POJ - 1456 贪心+并查集-白红宇

POJ - 1456 贪心+并查集

阅读量：4608 次

发布时间：2019-06-09

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

做法一：直接贪心，按照利润排序，然后直接尽量给每个活动安排到最晚的时间即可。时间复杂度O(n * d)当d都为10000时，很容易超时。由于这题数据比较水，所有贪心未超时。

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair
                 
                   typedef long long LL;const int maxn = 10000 + 5;struct node{ int prof, dead; bool operator < (const node &p) const { return prof > p.prof; }}a[maxn];int vis[maxn];int main() { int n; while(scanf("%d", &n) == 1) { for(int i = 0; i < n; ++i) { scanf("%d%d", &a[i].prof, &a[i].dead); } sort(a, a+n); memset(vis, 0, sizeof(vis)); int ans = 0; for(int i = 0; i < n; ++i) { int flag = 0; for(int j = a[i].dead; j > 0; --j) { if(!vis[j]) { flag = vis[j] = 1; break; } } if(flag) ans += a[i].prof; } printf("%d\n", ans); } return 0;}

做法二：先按照利润排序，然后并查集--当某个时间点被占据，它的下一个可用时间点为t - 1，将二者合并即可。复杂度n*logn

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair
                 
                   typedef long long LL;const int maxn = 10000 + 5;struct node{ int prof, dead; bool operator < (const node &p) const { return prof > p.prof; }}a[maxn];int p[maxn];int find(int x) { return x == p[x] ? x :p[x] = find(p[x]);} void unionset(int x, int y) { int rx = find(x), ry = find(y); if(rx != ry) p[rx] = ry;} int main() { int n; while(scanf("%d", &n) == 1) { for(int i = 0; i < maxn; ++i) p[i] = i; for(int i = 0; i < n; ++i) { scanf("%d%d", &a[i].prof, &a[i].dead); } sort(a, a+n); int ans = 0; for(int i = 0; i < n; ++i) { int u = find(a[i].dead); if(u > 0) ans += a[i].prof; unionset(a[i].dead, u-1); } printf("%d\n", ans); } return 0;}

做法三：利用优先队列，按照时间从大到小依次放入商品，保证当前的商品的截止期限都大于等于当前时间即可。可以理解为当有多个商品需要在同一天完成优先选择价值最大的。

复杂度O(n * lgn)

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair
                 
                   typedef long long LL;const int maxn = 1e4 + 5;struct node{ int prof, dead; }a[maxn];bool cmp(const node &a, const node &b) { return a.dead > b.dead;}bool operator < (const node &p1, const node &p2){ return p1.prof < p2.prof;}int main() { int n; while(scanf("%d", &n) == 1) { int maxt = 0; for(int i = 0; i < n; ++i) { scanf("%d%d", &a[i].prof, &a[i].dead); maxt = max(maxt, a[i].dead); } sort(a, a+n, cmp); priority_queue
                  
                   q; int ind = 0, ans = 0; for(int i = maxt; i > 0; --i) { while(ind < n && a[ind].dead == i) { q.push(a[ind++]); } if(!q.empty()) { ans += q.top().prof; q.pop(); } } printf("%d\n", ans); } return 0;}

如有不当之处欢迎指出！

转载于:https://www.cnblogs.com/flyawayl/p/8305333.html

你可能感兴趣的文章