HDU1050

题目链接

传送门

题目大意

题目大意就是在一个狭长的走廊里搬桌子,每次把桌子从一个房间搬到另一个房间,要求每次路径不能重叠 (可以同时搬路径不重叠的桌子),问至少需要多少时间能够搬完。

解题思路

贪心区间覆盖问题,算出每一段走廊走的次数,然后取最大值,因为每次搬消耗10分钟,所以最大值*10即为所求。

参考代码

#include <iostream>//数据输入输出流  
#include <string.h>//字符串操作函数  
#include <stdio.h>//C的输入输出  
#include <stdlib.h>//定义杂项函数及内存分配函数  
#include <math.h>//C中的数学函数  
#include <string.h>//c++中的string类 他不能用strcpy等c函数去操作  
#include <vector>//STL vetor容器  
#include <list>//STL list  
#include <map>// STL map  
#include <queue>// STL queue  
#include <stack>//sTL stack  
#include <bitset>//bitset可按位定义串  
//比如:bitset <1000> all;定义一个1000位的串  
#include <algorithm>//STL各种算法 比如 swap sort merge max min 比较  
#include <numeric>//常用数字操作 一般和algorithm搭配使用  
#include <functional>//STL定义运算函数(代替运算符)  
#include <limits.h>//定义各种数据类型最值常量  
using namespace std;  

int a[1000001];  

int main()  
{  
    #ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin);  
    #endif  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        memset(a , 0 , sizeof(a));  
        int n;  
        scanf("%d",&n);  
        while(n--)  
        {  
            int s , t;  
            scanf("%d%d",&s,&t);  
            s = (s - 1) / 2;  
            t = (t - 1) / 2;  
            int k;  
            if(s > t)  
            {  
                k = s;  
                s = t;  
                t = k;  
            }   
            for(int i = s ; i <= t ; i ++)  
                a[i] ++;  
        }  
        int maxx = -999999;  
        for(int i = 1; i <= 200 ; i ++)  
            if(a[i] > maxx)  
                maxx = a[i];  
        printf("%d\n",maxx * 10);     
    }  
}  

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图