文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>pku1083 Moving Tables

pku1083 Moving Tables

时间:2010-09-23  来源:Z_Q_2010



#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的搜索算法,因此效率很低,但可以用来理解贪心算法的工作原理。

相关阅读 更多 +
排行榜 更多 +
辰域智控app

辰域智控app

系统工具 下载
网医联盟app

网医联盟app

运动健身 下载
汇丰汇选App

汇丰汇选App

金融理财 下载