自动搬运

查看原文

来自洛谷，原作者为

	Ajwallet 厌倦追寻，一觅即中

搬运于2025-08-24 21:53:19，当前版本为作者最后更新于2018-04-23 21:13:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题第二个AC，第一篇题解

思路啊，就是贪心+离散化

乍看一下似乎是最大匹配，好像可以用导弹拦截的$70$分做法去做，但是时间复杂度为$O(n^3)$会超时，就打了一个贪心$O(n^2)$

要求的是最少的次数，那么我们可以发现，如果把每个比分都分成较大的较小的两部分，那么这样会使比赛更少。

如果要减少关键字的话，那就把大的积分排个序吧！这样就保证大积分不会干扰小积分的比赛数统计了（当然也可以排小积分）

这个时候小积分就构成了一个熟悉的题目：导弹拦截

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define zero(a) memset(a,0,sizeof(a))
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int t,n,x,y,f[1001],ans,p;
struct node
{
	int a,b;
}s[1001];//结构体
bool cmp(node x,node y){return x.b<y.b||x.b==y.b&&x.a<y.a;}//排序
int main()
{
	scanf("%d",&t);//输入
	while(t--)
	{
		zero(s);zero(f);//初始化
		scanf("%d",&n);//输入
		r(i,1,n)
		{
			scanf("%d-%d",&x,&y);//输入，scanf就是好
			s[i].b=max(x,y);//取下大积分
			s[i].a=min(x,y);//取下小积分
		}
		sort(s+1,s+n+1,cmp);//排个序
		ans=0;f[++ans]=s[1].a;//初始化
		r(i,2,n)
		{
			p=0;
			r(j,1,ans)
			 if(s[i].a>=f[j]&&f[p]<=f[j]) p=j;//比较丑的贪心
			if(!p)f[++ans]=s[i].a;else f[p]=s[i].a;//把它放进去
		}
		printf("%d\n",ans);//然后就输出
	}
}