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

原题链接：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