上海计算机学会2024年8月月赛C++乙组T1数字放置
发布时间
阅读量：
阅读量
数字放置
内存限制: 256 Mb时间限制: 1000 ms
题目描述
有一个无限长的一维表格，从左至右编号分别为 1,2,..., 以此类推。
小爱希望将 1 ~ n 之间的所有数字以此填写在表格中，对于每个数字有填写位置参数 li,ri，表示数字 i 仅可以填写在编号为 li 至编号为 ri 的格子内。
现给定填写的数字 n 及每个数字的填写位置参数 li,ri，问按此填写要求，是否能够将 1 ~ n 之间的所有数字填入表格中？可行则输出 YES ，反之输出 NO 。
输入格式
输入第一行，一个正整数 n 。
接下来n行，每行两个整数 li,ri 分别表示每个数字的填写位置参数
输出格式
输出共一行，YES 或 NO 表示答案。
数据范围
- 对于 30% 的数据，1≤n≤10，1≤li,ri≤100
- 对于 60% 的数据，1≤n≤103，1≤li,ri≤104
- 对于 100% 的数据，1≤n≤105，1≤li,ri≤109
样例数据
样例数据
输入:
3
1 3
2 3
1 2
输出:
YES
说明:
1 3 2 即可
输入:
4
1 3
2 3
1 2
1 3
输出:
NO
说明:
无法满足要求
解析：将各个区间排序，逐个合并区间，并判断是否能装下要装的数。
详见代码
#include<bits/stdc++.h>
using namespace std;
int n;
struct node {//单个数可以放入的区间
int left;//左边界
int right;//右边界
};
node a[100005];
//按左边界从小到大排序，左边界相同的按右边界从小到大排序
bool cmp(node x, node y) {
if (x.left == y.left) return x.right < y.right;
return x.left < y.left;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].left >> a[i].right;
}
sort(a + 1, a + n + 1, cmp);//排序
int cnt = 0;//当前区间内需要保存几个数
int r = -1;//当前区间右边界
int l = 0;//当前区间左边界
for(int i = 1; i <= n; i++) {
//如果新区间与当前区间没有重合，当前区间改为新区间
if (i == 1 || a[i].left > r) {
cnt = 1;
l = a[i].left;
r = a[i].right;
} else {//有重合，则合并区间
cnt++;
//如果新区间左边界不同于当前区间左边界
if (a[i].left != l) {
cnt -= a[i].left - l;//将数尽量装进新区间前面
if (cnt < 1) cnt = 1;//至少剩下当前数
}
l = a[i].left;//左边界为新区间左边界
r = max(r, a[i].right);//右边界为新区间和当前区间右边界的最大值
if (r - l + 1 < cnt) {//如果当前区间装不下要装的数
cout << "NO";//输出no
return 0;
}
}
}
cout << "YES";
return 0;
}
只能得70分，这个代码处理不了形如下的数据：
4
1 5
2 3
2 3
2 3
更新后的代码在上一版代码的基础上使用贪心思想，使用优先队列把区间右边界加入优先队列，优先安排右边界小的。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
struct node {//单个数可以放入的区间
int left;//左边界
int right;//右边界
};
node a[100005];
//按左边界从小到大排序，左边界相同的按右边界从小到大排序
bool cmp(node x, node y) {
if (x.left == y.left) return x.right < y.right;
return x.left < y.left;
}
priority_queue <int,vector<int>,greater<int>> pq;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].left>>a[i].right;
}
sort(a+1,a+n+1,cmp);//排序
int lp;//最小可以安排数的位置
for(int i=1;i<=n;i++){
if (i==1||lp==a[i].left){//如果是第一个，或者区间最小值为lp
lp=a[i].left;//lp为区间最小值
pq.push(a[i].right);//右区间加入优先队列
}else{//如果左区间大于lp
//把lp到左区间都安排上，优先安排右区间小的
while(!pq.empty()&&lp<a[i].left){
if (pq.top()>=lp){//如果右区间大于等于lp，安排到lp的位置
pq.pop();//安排完的弹掉
lp++;//下一个待安排的位置
}else{//如果右区间小于lp，则安排不了
cout<<"NO";//打印NO，退出
return 0;
}
}
lp=a[i].left;//更新可安排的最小位置
pq.push(a[i].right);//右区间加入优先队列
}
}
while(!pq.empty()){//还有没安排的
if (pq.top()>=lp){//能安排，安排到lp位置
pq.pop();
lp++;
}else{//不能安排，打印NO并退出
cout<<"NO";
return 0;
}
}
cout<<"YES";
return 0;
}
简化后：
#include<bits/stdc++.h>
using namespace std;
int n;
struct node {//单个数可以放入的区间
int left;//左边界
int right;//右边界
};
node a[100005];
bool cmp(node x, node y) {
if (x.left == y.left) return x.right < y.right;
return x.left < y.left;
}
priority_queue <int,vector<int>,greater<int>> pq;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].left>>a[i].right;
}
sort(a+1,a+n+1,cmp);//排序
int lp=0;//最小可以安排数的位置
for(int i=1;i<=n+1;i++){
if(a[i].left!=lp){
while(!pq.empty()&&(lp<a[i].left||i==n+1)){
if (pq.top()>=lp){//如果右区间大于等于lp，安排到lp的位置
pq.pop();//安排完的弹掉
lp++;//下一个待安排的位置
}else{//如果右区间小于lp，则安排不了
cout<<"NO";//打印NO，退出
return 0;
}
}
}
lp=a[i].left;//更新可安排的最小位置
pq.push(a[i].right);//右区间加入优先队列
}
cout<<"YES";
return 0;
}
全部评论 (0)
还没有任何评论哟~