肖宇睿
(人畜无害的小学生)
1
RE代码
#include<bits/stdc++.h>
using namespace std;
long long n,m;
unordered_multiset<int>st;
int a[100005],l[100005],r[100005],mx=0;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>l[i]>>r[i];
for(int j=l[i];j<=r[i];j++){
st.insert(j);
}
}
for(int i=1;i<=m;i++){
unordered_multiset<int> st1;
st1=st;
for(int j=l[i];j<=r[i];j++){
st1.erase(st1.find(j));
}
unordered_set<int>st2;
for(auto i:st1){
st2.insert(i);
}
// for(auto i:st1)
// cout<<i<<" ";
//
// cout<<endl;
a[i]=st2.size();
if(a[i]>=a[mx]){
mx=i;
}
}
cout<<mx<<" "<<n-a[mx];
return 0;
}
到底为什么RE啊！
2 个赞
肖宇睿
(人畜无害的小学生)
3
2. 没有被选中的区间
题目ID：8467拓展题100分
最新提交：
Runtime Error
21 分
历史最高：
Runtime Error
21 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
时间：1s 空间：256M
题目描述：
数轴上有 n 个点，编号为 1 到 n 。
小信有 m 个区间，区间可能有重叠。小信要选出 m−1 个区间覆盖尽可能多的点。在这之后，小信想知道没被覆盖的点的数量，以及没有选中的区间的编号，如果有多个满足条件的区间，输出最大的那个。
输入格式：
第一行包含两个整数 n , m 。
接下来 m 行，每行包含两个整数 L_i , R_i
输出格式：
输出两个整数，第一个整数表示没有被选中的区间编号，如果有多个满足条件的区间，输出最大的那个，编号从 1 开始；第二个数表示没有被覆盖的点的数量。
样例1输入：
10 4
1 6
4 9
3 4
5 8
样例1输出：
4 1
约定：
对于 100\% 的数据, 1 \le n,m \le 10^5 , 1≤L_i≤R_i≤n 。
对于样例1：
不选择第 1 个区间，有 3 个点没有被覆盖到，分别是 [1,2,10] ；
不选择第 2 个区间，有 2 个点没有被覆盖到，分别是 [9,10] ；
不选择第 3 个区间，有 1 个点没有被覆盖到，分别是 [10] ；
不选择第 4 个区间，有 1 个点没有被覆盖到，分别是 [10] 。
所以不选择 3 或者 4 区间，没被覆盖到的点数最小，都是 1 。