牛客練習試合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:
リンク: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;
}