百度之星2017初赛B1006 小小粉丝度度熊
2024-08-30 11:32:56
思路:
考虑到补签卡一定是连续放置才更优,所以直接根据起始位置枚举。预先处理区间之间的gap的前缀和,在枚举过程中二分即可。复杂度O(nlog(n))。
实现:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll; const ll INF = 0x3f3f3f3f; int main()
{
int n, m;
while (scanf("%d %d", &n, &m) != EOF)
{
vector<pair<int, int>> v;
int x, y;
for (int i = ; i < n; i++)
{
scanf("%d %d", &x, &y);
v.push_back(pair<int, int>(x, y));
}
sort(v.begin(), v.end());
vector<pair<int, int>> res;
res.push_back(v[]);
for (int i = ; i < v.size(); i++)
{
if (v[i].first > res.back().second + ) res.push_back(v[i]);
else res.back().second = max(res.back().second, v[i].second);
}
vector<ll> sum(res.size() - );
for (int i = ; i < res.size() - ; i++)
sum[i] = (ll)res[i + ].first - - res[i].second;
sum.push_back(INF);
for (int i = ; i < sum.size(); i++)
sum[i] += sum[i - ];
ll maxn = ;
for (int i = ; i < sum.size(); i++)
{
ll tmp = (i == ? : sum[i - ]);
int pos = upper_bound(sum.begin() + i, sum.end(), m + tmp) - sum.begin();
ll tmp2 = (pos == i ? m : m - (sum[pos - ] - tmp));
maxn = max(maxn, res[pos].second - res[i].first + + tmp2);
}
printf("%lld\n", maxn);
}
return ;
}
最新文章
- Hibernatel框架基础使用
- Autofac
- poj 3621 二分+spfa判负环
- [原创] WINDOWS 7 精简教程之驱动精简 可用于64和32
- String reorder
- Java动手实验及课后程序
- 使用 Feedly RSS阅读器订阅技术大牛的博客
- 让python输出不自行换行的方法
- Java 面向对象(转)
- 【leetcode】Candy(python)
- pudn下载地址的规律
- MAC 相关操作解析
- [笔记]《JavaScript高级程序设计》- JavaScript简介
- ORA-01940: cannot drop a user that is currently connected解决方法
- oracle INS-13001 环境不满足最低要求
- Nmap参考指南(Man Page)
- Sonar+maven+jenkins集成,Java代码走查
- CocosCreator小栗子
- 题目1018:统计同成绩学生人数(数组或者map)
- git分支流
热门文章
- java多线程synchronized volatile解析
- hdu 1811拓扑排序+并查集(容器实现)
- Linux下汇编语言学习笔记80 ---
- 微软消息队列MessageQueue(MQ)
- 联想S820 MIUI刷机包 MIUI 4.4.30 流畅执行 在线主题破解
- 百度LBS云搜索时报错 &;quot;filter:area is not filteable field, please set property in the cloud-storage
- 嵌入式C语言经常使用keyword
- Codeforces Round #325 (Div. 2) B. Laurenty and Shop 前缀+后缀
- 重启标志log
- 在PL/SQL使用游标获取数据及动态SQL