Codeforecs-690-div3

DIV3-F

思考：
题意很明显就是说一个数组每个元素都是一个区间，然后如果有一个区间可以和其余所有区间都有交集那么就是完美的。最少删除多少个可以成为完美的。很明显，先排序一下，然后枚举其中一个区间，然后看看有多少区间和他没有交集。但是这是n*n的复杂度。但很明显有多少和区间[l,r]没有交集的不就是L>r或者Rr的。但是区间数据范围很大，所以要离散化一下，然后遍历一遍即可，这里我用了树状数组，其实前缀和也一样。

结论：
枚举每个区间[l,r]，然后求出L>r和Rr，R不可能再

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#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
#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 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< 
总结：
 对于cf要往下看，并不是那么难，寻找思路和注意细节是重要的。

Codeforecs-690-div3

C/C++/C#相关栏目本月热门文章