POJ 1083 Moving Tables-白红宇

POJ 1083 Moving Tables

阅读量：4981 次

发布时间：2019-06-12

本文共 899 字，大约阅读时间需要 2 分钟。

题意：一个建筑物里有400个房间，房间都在一层里，在一个走廊的两侧，如图，现在要搬n张桌子，告诉你每张桌子是从哪个屋搬到哪个屋，搬桌子的线路之间不可以有重叠，问最少搬几次。

解法：贪心。一开始觉得只要排个序，然后按顺序一次一次的分配就可以了……但是wa了……百度之后知道只要看哪块地的使用次数最多就是答案……于是A了之后出随机数据对拍，发现确实一开始的贪心是错的……嘤嘤嘤

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;bool cmp(int a, int b){ return a > b;}int main(){ int T; while(~scanf("%d", &T)) { while(T--) { int n; int ans[200] = {0}; scanf("%d", &n); for(int i = 0; i < n; i++) { int l, r; scanf("%d%d", &l, &r); if(l > r) swap(l, r); if(l & 1) l++; if(r & 1) r++; for(int i = l; i <= r; i += 2) ans[i / 2]++; } sort(ans, ans + 200, cmp); printf("%d\n", ans[0] * 10); } } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4849038.html

你可能感兴趣的文章