首页 / 更多教程 / POJ 1083 Moving Tables 思路 难度:0

POJ 1083 Moving Tables 思路 难度:0

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了POJ 1083 Moving Tables 思路 难度:0，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1108字，纯文字阅读大概需要2分钟。

内容图文

http://poj.org/problem?id=1083

　　这道题题意是有若干段线段,每次要求线段不重叠地取,问最少取多少次.

　　因为这些线段都是必须取的,所以需要让空隙最小

思路:

　　循环直到线段全部取完,对于某个刚取得线段ij,下一个线段km取起点k尽量靠近j且满足k>j的.记录循环次数cnt,答案是cnt*10

注意:

　　房间是相对的,也就是说对于奇数房间号,利用的走廊相当于对应的偶数房间号开始的那一段路程,

　　一段路程的开头不能是另外一段路程的结尾.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 400;
int n;
typedef pair<int,int> P;
P a[maxn];
bool vis[maxn];
int main()
{
    freopen("data.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 0;i < n;i++)
        {
            scanf("%d%d",&a[i].first,&a[i].second);
            if(a[i].first&1)a[i].first++;
            if(a[i].second&1)a[i].second++;
            if(a[i].first>a[i].second)swap(a[i].first,a[i].second);
        }
        sort(a,a+n);
        memset(vis,false,sizeof(vis));
        int cnt = 0;
        for(int st = 0;st < n;st++)
        {
            if(vis[st])continue;
            vis[st] = true;
            cnt++;
            for(int i = st + 1,e = a[st].second;i < n;i++)
            {
                if(a[i].first <= e || vis[i])continue;
                vis[i] = true;
                e = a[i].second;
            }
        }
        printf("%d\n",cnt * 10);
    }
    return 0;
}

 

原文：http://www.cnblogs.com/xuesu/p/4639739.html

内容总结

以上是互联网集市为您收集整理的POJ 1083 Moving Tables 思路 难度:0全部内容，希望文章能够帮你解决POJ 1083 Moving Tables 思路 难度:0所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1228685.html

来源：【匿名】