题目描述
xxx
样例
xx
算法1
(贪心) O(nlogn)
发现题解写的都不是很仔细,我发一篇
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
struct node{//结构体存方便
int w,v;
bool operator<(const node&a)const{//优先队列用的,重载运算符
return v>a.v;
}
}a[N];
bool cmp(node a,node b){//排序用的
if(a.w==b.w)return a.v>b.v;
return a.w<b.w;
}
int main(){
cin.tie(0);
cin>>n;
priority_queue<node>p;
for(int i=1;i<=n;++i)scanf("%d %d",&a[i].w,&a[i].v);//cin好像会报超时
sort(a+1,a+1+n,cmp);
int d=0,res=0;
for(int i=1;i<=n;++i){//没超过期限直接放,超过就比较做过作业中的最小值,然后替换,就是最大的
if(d<a[i].w){
d++;
p.push(a[i]);
res+=a[i].v;
}
else if(p.size()&&p.top().v<a[i].v){
int j=p.top().v;
p.pop();
p.push(a[i]);
res+=a[i].v-j;
}
}
//while(p.size()){cout<<p.top().v<<endl;p.pop();}//degub,莫名其妙就过了
cout<<res;
}
blablabla