题解 P3845 【[TJOI2007]球赛】

· · 题解

本题第二个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);//然后就输出
    }
}