SGU 548 Dragons and Princesses-白红宇

SGU 548 Dragons and Princesses

阅读量：6151 次

发布时间：2019-06-21

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

意甲冠军：

n个月格儿所有的格龙或公主的儿子从勇士1走n 不杀杀死有钱拿路过公主假设之前杀龙的数量满足公主要求就会停止行走问勇士想多拿钱可是必需要满足n格子的公主最多拿多少钱

思路：

公主仅仅限制杀龙的数量因此不想停下来结婚就控制杀龙的数量就可以假设要放弃一些龙那么一定会贪心放弃钱少的龙最后推断一下能不能和n格子的公主结婚就可以

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define N 200010int n;struct dragon { int x, id; bool operator<(const dragon ff) const { return x > ff.x; }} now;priority_queue
                 
                   q;int ans[N], tot, sum;int main() { int i, k, s; char who[100]; while (!q.empty()) q.pop(); scanf("%d", &n); for (i = 2; i <= n; i++) { scanf("%s%d", who, &k); if (i == n) break; if (who[0] == 'd') { now.x = k; now.id = i; q.push(now); } else { s = q.size(); if (s >= k) { k = s - k + 1; while (k--) q.pop(); } } } s = q.size(); if (s < k) printf("-1\n"); else { tot = sum = 0; while (!q.empty()) { now = q.top(); q.pop(); sum += now.x; ans[tot++] = now.id; } printf("%d\n", sum); printf("%d\n", tot); sort(ans, ans + tot); for (i = 0; i < tot; i++) printf("%d%s", ans[i], (i == tot - 1) ? "\n" : " "); } return 0;}

你可能感兴趣的文章