思考:
题意很明显就是说一个数组每个元素都是一个区间,然后如果有一个区间可以和其余所有区间都有交集那么就是完美的。最少删除多少个可以成为完美的。很明显,先排序一下,然后枚举其中一个区间,然后看看有多少区间和他没有交集。但是这是n*n的复杂度。但很明显有多少和区间[l,r]没有交集的不就是L>r或者R<l的的那些区间,然后就维护两个前缀和,一个维护L的vb一个维护R的vc,然后求的时候看看有多少从vc中<l的,然后多少从vb中>r的。但是区间数据范围很大,所以要离散化一下,然后遍历一遍即可,这里我用了树状数组,其实前缀和也一样。
结论:
枚举每个区间[l,r],然后求出L>r和R<l的区间有多少个。值得注意的是,这样并不会有重复,既然L>r,R不可能再<l了,所以并不会多算。
代码:
#include<iostream>
#include<cstring>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
//#pragma GCC optimize(2)
#define eps 1e-9
#define fi first
#define se second
#define pb push_back
#define db double
#define ll long long
#define PII pair<int,int >
#define cin(x) scanf("%d",&x)
#define cout(x) printf("%d ",x)
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int ll
using namespace std;
const int N = 5e5,M = 2000;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const double pai = acos(-1);
int T,n,m;
PII va[N];
int vb[N],vc[N];
int minn = inf,maxnl = 0,maxnr = 0;
vector<int > v;
int getid(int x);
int bit(int x);
int query(int x,int va[]);
void update(int x,int value,int va[]);
signed main()
{
IOS;
cin>>T;
while(T--)
{
cin>>n;
v.clear();
minn = inf,maxnl = 0,maxnr = 0;
for(int i=1;i<=n;i++)
{
cin>>va[i].fi>>va[i].se;
v.pb(va[i].fi);
v.pb(va[i].se);
maxnl = max(maxnl,va[i].fi);
maxnr = max(maxnr,va[i].se);
}
sort(va+1,va+1+n);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
maxnl = getid(maxnl),maxnr = getid(maxnr); //注意这里也要离散化喔
for(int i=0;i<=max(maxnl,maxnr);i++) vb[i] = vc[i] = 0;
for(int i=1;i<=n;i++)
{
int l = getid(va[i].fi),r = getid(va[i].se);
update(l,1,vb);
update(r,1,vc);
}
for(int i=1;i<=n;i++)
{
int l = getid(va[i].fi),r = getid(va[i].se);
int res = query(l-1,vc)+query(maxnl,vb)-query(r,vb);
minn = min(minn,res);
}
cout<<minn<<"\n";
}
return 0;
}
int getid(int x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int bit(int x)
{
return x&(-x);
}
int query(int x,int va[])
{
int sum = 0;
while(x)
{
sum += va[x];
x -= bit(x);
}
return sum;
}
void update(int x,int value,int va[])
{
while(x<=max(maxnl,maxnr))
{
va[x] += value;
x += bit(x);
}
}
总结:
对于cf要往下看,并不是那么难,寻找思路和注意细节是重要的。