当前位置: 首页 > 工具软件 > potion > 使用案例 >

C1. Potions (Easy Version)(cf) 优先队列、后悔贪心

南宫兴德
2023-12-01

原题链接:Problem - 1526C1 - Codeforces

题目大意:给你n个数,要你从左到右选择,要sum一直>=0,问你最多可以取多少个数。

这不是普通的01背包了,这个题是有顺序的,可能从前往后有顺序的时候就会有sum<0的时候,所以这里用到优先队列+后悔贪心

1.有四种情况:

1)a[i]>=0, 直接取, cnt++;

2)a[i] < 0 但是sum + a[i] >= 0,也可以取,但是要把负数存到优先队列,存它的绝对值,cnt++;

3)a[i] < 0 且sum + a[i] < 0 但是队列不为空且队列中绝对值最大的那个绝对值大于a[i]的绝对值,可以把这个最大的绝对值取出来,然后把a[i]的绝对值入队,sum += a[i] + q.top(),这个时候cnt不用改变,相当于替换了,想想,替换成一个负数绝对值更小的,后面就更有机会加别的负数;

4)a[i] < 0且sum + a[i] < 0且队列中没有数或者队列中的数都小于等于a[i]的绝对值,那么不进行操作(不取)。

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

int main(){
  int n, temp;
  cin >> n;
  priority_queue<int> q;
  ll sum = 0, cnt = 0;
  rep(i, n){
    cin >> temp;
    if(temp >= 0){
      sum += temp;
      cnt++;
    } 
    else{
      if(sum + temp >= 0){
        q.push(abs(temp));
        cnt++;
        sum += temp;
      }
      else if(q.size() && abs(temp) < q.top()){ //把负数的绝对值存进数组
        sum += q.top() + temp;
        q.pop();
        q.push(abs(temp));
      }
    }
    // cout << cnt << "**" << endl;
  }
  cout << cnt;
  return 0;
}

文章参考:https://blog.csdn.net/lucifer1214/article/details/117390055 

 类似资料: