nyoj 220 推桌子 poj 1083

曾经终败给现在 2022-08-26 14:19 137阅读 0赞

题意：

给出一些区间，让你每次从中选取一些互不相交的区间，让选择次数最少。

解法：贪心 或 dp

贪心思路：

首先按初始点排序，然后依次向后能选择可以加入的，不能加入的第二次选择，输出次数即可、

代码：

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    struct Node
    {
        int a,b;
    };
    Node s[300];
    int ans[300];
    int comp(Node x,Node y)
    {
        if(x.a!=y.a)
            return x.a<y.a;
    }
    int main()
    {
        int T,n;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            int cmx,cmy;
            for(int i=0; i<n; i++)
            {
                scanf("%d%d",&cmx,&cmy);
                cmx=(cmx+1)/2,cmy=(cmy+1)/2;
                if(cmx>cmy)
                {
                    int temp=cmx;
                    cmx=cmy;
                    cmy=temp;
                }
                s[i].a=cmx,s[i].b=cmy;
            }
            sort(s,s+n,comp);
            int cas=0,last;
            memset(ans,0,sizeof(ans));
            for(int i=0; i<n; i++)
            {
                if(ans[i]==0)
                {
                    //printf("%d %d\n",s[i].a,s[i].b);
                    last=s[i].b;
                    ans[i]=1;
                    cas++;
                    for(int j=i+1; j<n; j++)
                    {
                        if(ans[j]==0&&s[j].a>last)
                        {
                            last=s[j].b;
                            ans[j]=1;
                        }
                    }
                }
            }
            printf("%d\n",cas*10);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 995硬币找零（dp）递推

递推：（自底向上，从小到大）　　　　由递推关系式：dp(T) = min(dp(T - vi)) + 1, 其中T-vi < T是恒成立，因此可以保证从小大到递推，在计算d

绝地灬酷狼/ 2024年02月17日 19:19/ 0 赞/ 66 阅读

相关贪心算法———房间搬桌子

题目描述著名的ACM（Advanced Computer Maker）公司租用了一层有400个房间的办公室，结构如表1所示。表1 ACM公司办公楼室示意图 <t

骑猪看日落/ 2023年10月05日 15:59/ 0 赞/ 5 阅读

相关 POJ 2506 Tiling 递推+大数

将答案存在ret数组里面 n=0的时候居然是1 递推关系 ret[i] = ret[i-1] + ret[i-2]2 ; 注意是乘2不是3，当ret\[i

拼搏现实的明天。/ 2023年06月16日 12:56/ 0 赞/ 18 阅读

相关状态压缩经典题目（poj1184 nyoj81）

题目描述：描述司令部的将军们打算在N\M的网格地图上部署他们的炮兵部队。一个N\M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"

深碍√TFBOYSˉ_/ 2022年08月27日 02:27/ 0 赞/ 126 阅读

相关 nyoj 220 推桌子 poj 1083

题意：给出一些区间，让你每次从中选取一些互不相交的区间，让选择次数最少。解法：贪心或 dp 贪心思路：首先按初始点排序，然后依次向

曾经终败给现在/ 2022年08月26日 14:19/ 0 赞/ 138 阅读

相关 POJ1019 数学+递推乱搞

有一个字符串的形式是这样的112123123412345123456123456712345678123456789123456789101234567891011123456

╰+攻爆jí腚メ/ 2022年08月22日 15:24/ 0 赞/ 159 阅读

相关南阳题目220-推桌子

推桌子时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述 The famous ACM (Advanced Computer Make

客官°小女子只卖身不卖艺/ 2022年07月27日 11:51/ 0 赞/ 128 阅读

相关 POJ1083 Moving Tables

题目大意：走廊中搬桌子，走廊的宽度只允许一张桌子通过，但允许路线不交叉的同时搬桌子，每次搬桌子都需要10分钟，问所需最短时间。解题思路：统计搬桌子过程中经过每个房

浅浅的花香味﹌/ 2022年07月11日 08:47/ 0 赞/ 146 阅读

相关 hdu-1083-Courses

题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=1083][http_acm.hdu.edu.cn_showproblem.ph

以你之姓@/ 2022年05月19日 06:20/ 0 赞/ 145 阅读

相关 POJ1083Moving Tables（简单模拟）

题目链接：[http://poj.org/problem?id=1083][http_poj.org_problem_id_1083] 如图所示在一条走廊的两侧各有20

﹏ヽ暗。殇╰゛Y/ 2021年12月03日 13:09/ 0 赞/ 259 阅读