B. Ideal Point
思路
- 首先删除不包含点k的线段，因为这些线段对使\(f(k) > f(x)\)没有贡献
- 然后再考虑剩余的线段中覆盖得到的f(x)最大值是否唯一（由于前面的处理，所有线段均包含点k，如果最大值唯一的话，那么只能是k点）,如果最大值不唯一的话就无论如何删除线段也无法满足要求（由于所有线段均包含点k，如果想要让其他最大值减小的话，f(x）也会随之减小，因此此时删边没有任何意义）
代码1差分与前缀和
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
const int M = 2e5+10;
int d[55];
void solve(){
int t;
cin >> t;
while(t -- ){
memset(d,0,sizeof d);
int n,k;
cin >> n >> k;
while(n --){
int l,r;
cin >> l >> r;
if(l > k || r < k)continue;
d[l] ++;
d[r + 1] --;
}
int maxn = 0,maxp = 0;
for(int i = 1; i <= 50; i ++ ){
d[i] += d[i - 1];
if(d[i] > maxn){
maxn = d[i];
maxp = i;
}
}
if(maxp == k && d[k - 1] != d[k] && d[k + 1] != d[k])cout << "yes" << nl;
else cout << "no" << nl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
代码2
可以维护所有线段的公共区间快速判断，如果最后所有线段的公共区间长度为1则yes，否则no
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
const int M = 2e5+10;
void solve(){
int t;
cin >> t;
while(t -- ){
int n,k;
cin >> n >> k;
int L = 0,R = 114514;
while(n --){
int l,r;
cin >> l >> r;
if(l > k || r < k)continue;
L = max(L,l);
R = min(R,r);
}
if(L == R)cout << "yes" << nl;
else cout << "no" << nl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}