pku1083 Moving Tables


#include<stdio.h>
#include<algorithm>
using namespace std;

const int Maxn=405;
int g[Maxn];

int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {
        int n;
        scanf("%d",&n);
        memset(g,0,sizeof(g));
        for(int i=1;i<=n;i++)
        {
            int s,t;
            scanf("%d%d",&s,&t);
            if(s>t) swap(s,t);
            if(s%2==0) s--;
            if(t%2==1) t++;
            for(int j=s;j<=t;j++) g[j]++;
        }
        int num=0;
        for(int i=1;i<=400;i++) if(g[i]>num) num=g[i];
        printf("%d\n",num*10);
    }
    return 0;
}


总结：

这道题就是算法导论贪心算法那一章后面习题的教室选择问题，它不能用活动选择算法来重复操作几次直至选择了所有的活动来确定教室数等于使用活动选择的次数。因为在某些情境下是错的，具体可以看该题的discuss。那道习题提示采用图着色，亦即不兼容的两个活动间连一条边，最后涂色时相连的两个活动涂不同的颜色，最后总共所需的颜色数就是教室数。图着色采用类似dfs的搜索算法，因此效率很低，但可以用来理解贪心算法的工作原理。