【习题 8-15 UVA - 1617】Laptop
2024-08-31 16:54:30
【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
贪心。
把所有的区间按照右端点为第一关键字,左端点为第二关键字升序排。
然后令now = a[i].second.
(now即当前的连续区间的最右端点
即第一个区间的右端点。
第一个点就应该放在这个地方。
然后对于第i+1个区间。
如果now==a[i+1].second
则把第i+1个点放在之前一连串的点的最左边的左边一个位置。
然后now保持不变
(保证有解的话,肯定是有空位置的,之前连续放的点不可能充满整个第i+1个区间的
如果now<a[i+1].first
就说明中间一定会出现gap.
则gap++,now=a[i+1].second
如果now>=a[i+1].first
则令now递增1,连续放
因为now==a[i+1].second之后,会一直往前放。
所以不会出现now>a[i+1].second的情况。
题目中那个条件"r[i]<=r[j] <=> l[i]..l[j]"的约束,使得这个题有特殊性一点吧。
即不会出现一个区间完全包含另外一个区间。
感觉这题有点奇怪。
就不想再管他啦。
【代码】
/*
1.Shoud it use long long ?
2.Have you ever test several sample(at least therr) yourself?
3.Can you promise that the solution is right? At least,the main ideal
4.use the puts("") or putchar() or printf and such things?
5.init the used array or any value?
6.use error MAX_VALUE?
7.use scanf instead of cin/cout?
8.whatch out the detail input require
*/
/*
一定在这里写完思路再敲代码!!!
*/
#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> > v;
bool cmp(pair<int,int> a,pair<int,int> b){
if (a.second==b.second)
return a.first<b.first;
else
return a.second<b.second;
}
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while (T--){
cin >> n;
v.clear();
for (int i = 0;i < n;i++){
int x,y;
cin >> x >> y;
v.push_back(make_pair(x,y));
}
sort(v.begin(),v.end(),cmp);
int gap = 0;
int now = v[0].second;
for (int i = 1;i < (int)v.size();i++){
if (v[i].second==now) continue;
if (now<v[i].first){
gap++;
now = v[i].second;
}else{
now++;
}
}
cout <<gap<<endl;
}
return 0;
}
最新文章
- Google Code Jam 2016 Round 1B B
- swf格式文件如何修改里面的动作路径或者动作脚本(没有源文件的情况)
- Odoo 配置快速创建编辑按钮
- C#操作串口总结
- C语言小知识
- HW4.1
- linux系统下安装wget。
- [Android学习笔记]PopupWindow的使用
- jquery 弹出登陆框,简单易懂!修改密码效果代码
- 数列的前N项之和
- w3school之CSS学习笔记
- 一口一口吃掉Volley(四)
- 初步谈谈 C# 多线程、异步编程与并发服务器
- Ext.isNumber与Ext.isNumeric
- silverlight中 设置 头像(添加图片)
- python selenium+phantomJS自动化测试环境
- vue-9-动画
- 中国网建提供的SMS短信发送
- Git安装遇到的问题fatal: Could not read from remote repository.的解决办法
- JavaScript学习(1)之JavaScript基础