牛客練習試合50 C.tokitsukaze and Soldier(優先キュー+欲張り)

9240 ワード

C.tokitsukaze and Soldier
リンク:https://ac.nowcoder.com/acm/contest/1080/C
出典:牛客網
タイトルの説明
1つのゲームでは、tokitsukazeはn人の兵士の中からいくつかの兵士を選んで団を構成してコピーを打つ必要があります.第iの兵士の戦力はv[i]であり、団の戦力は団内のすべての兵士の戦力の和である.しかし、これらの兵士には特別な要求がある.i番目の兵士を選んだら、この兵士希望団の人数はs[i]を超えない.△第iの兵士を選ばなければ、この制限はありません.tokitsukazeは、団の戦力が最大でどれだけ大きいか知りたい.
説明を入力:
第1行は正の整数n(1≦n≦10^5)を含む.次にn行、各行は2つの正の整数v,s(1≦v≦10^9,1≦s≦n)を含む.
出力の説明:
正の整数を出力し、団の最大戦力を表す.
分析:
sの大きいものから小さいものまで並べ替えて、優先行列(小根の山)はすでに選択した兵士の戦力vの大きいものから小さいものまでsを保存して、すでに選択した兵士の人数はきっと現在選択したsより小さいもし現在の兵士を選択した後に人数の制限を超えたら、vの最小の兵士に人数の制限を満たすことを知らせます
毎回の結果に対してmaxを取るのが答えです
code:
#include
#include
#include
#include
#include
#include
typedef long long ll;
const int inf=0x3f3f3f3f;
const int inn=0x80808080;
using namespace std;
const int maxm=1e5+5;
struct Node{
    int v,s;//v   ,s     
}a[maxm];
bool cmp(Node a,Node b){
    return a.s>b.s;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].v>>a[i].s;
    }
    sort(a+1,a+1+n,cmp);
    ll ans=0;//    
    ll now=0;//    
    int num=0;//    
    int limit=inf;//    
    priority_queue<ll,vector<ll>,greater<ll>>q;
    for(int i=1;i<=n;i++){
        limit=min(limit,a[i].s);
        q.push(a[i].v);
        num++;
        now+=a[i].v;
        while(num>limit){
            ll x=q.top();
            q.pop();
            now-=x;
            num--;
        }
        ans=max(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}