刚刚结束的cf div3 E题
  • 板块学术版
  • 楼主wanttoac
  • 当前回复9
  • 已保存回复9
  • 发布时间2024/5/21 00:59
  • 上次更新2024/5/21 16:17:57
查看原帖
刚刚结束的cf div3 E题
1258100
wanttoac楼主2024/5/21 00:59

用的反悔贪心的思路,样例都过了但最后为什么会WA\newline

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct month{
   int c,h;
   bool operator <(const month &a) const {
      return c<a.c;
   }
}m[55];
signed main(){
   int t;
   cin>>t;
   while(t--){
      priority_queue<month>happy;
      int n,x;
      cin>>n>>x;
      for(int i=1;i<=n;i++)cin>>m[i].c>>m[i].h;
      int sum=0;
      int money=0;
      for(int i=1;i<=n;i++){
         if(money>=m[i].c){
            money-=m[i].c;
            sum+=m[i].h;
            happy.push(m[i]);
         }
         else{
            vector<month>item;
            while(!happy.empty()){
               if(money+happy.top().c>=m[i].c&&happy.top().h<=m[i].h){
                  sum+=m[i].h-happy.top().h;
                  money=money+happy.top().c-m[i].h;
                  happy.pop();
                  happy.push(m[i]);
                  break;
               }
               else{
                  item.push_back(happy.top());
                  happy.pop();
               }
            }
            for(int i=0;i<item.size();i++)happy.push(item[i]);
         }
         money+=x;
      }
      cout<<sum<<endl;
   }
}
2024/5/21 00:59
加载中...