【每日一题】贪心、滑动窗口
题目连接：https://ac.nowcoder.com/acm/problem/50439
【思路】
看到题目盲猜贪心，一开始是想着按val排序，每次取可以取的大值，但是涉及到容量大于限制的人数时 不容易去判断是删掉限制了我们人数的那个人扩充容量还是按现在的限制把多的人都删掉；改为按容量排序，这道题就很容易解了；
按容量从大到小排序一遍，一次遍历，当s值变化时，把多于s的小值（使用最小堆）都拿出去，若此时堆顶的值小于当前值 && 容量为s，用当前值替换掉堆顶值。
判断s值是否变化 维护一个prevs变量即可
【心得】
做题要力争一次AC
一开始写了个错误解法，原因自己分析是脑子不够好使却不愿意多写代码（其实是重复的），
倒不如写一个每种情况枚举的代码，然后再根据此写优化代码，没必要一次写最优代码
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
char s[22][100100];
typedef struct{
int v;
int s;
}Node;
int cmp(const void*a,const void*b){
Node p1=*(Node*)a;
Node p2=*(Node*)b;
if(p1.s!=p2.s) return p2.s-p1.s;
return p2.v-p1.v;
}
priority_queue<int,vector<int> , greater<int>> pq;//小顶堆
int main(void) {
Node num[maxn];
int n;cin>>n;int i,j;
for(i=0;i<n;++i){
scanf("%d %d",&num[i].v,&num[i].s);
}
qsort(num,n,sizeof(Node),cmp);
ll ans=0;
ll sum=0;
int prevs=0;
for(i=0;i<n;++i)
{
if(prevs != num[i].s) prevs=num[i].s;
int v=num[i].v;
while(pq.size()>prevs){
sum-=pq.top();
pq.pop();
}
if(pq.size()<prevs) {
pq.push(v);
sum+=v;
}else if(pq.size()==prevs && pq.top() < v){
sum-=pq.top();
pq.pop();
pq.push(v);
sum+=v;
}
ans=max(ans,sum);
}
cout << ans;
return 0;
}
错误代码：
for(i=0;i<n;++i)
{
if(prevk != num[i].s) prevk=num[i].s;
while(pq.size()>=prevk && pq.top()<num[i].v){
sum -= pq.top();
pq.pop();
}
pq.push(num[i].v);
sum+=num[i].v;
ans=max(ans,sum);
} 看完标程，自己想麻烦了=。= for(i=0;i<n;++i)
{
int v = num[i].v;
pq.push(v);
sum+=v;
while(pq.size()>num[i].s){
sum-=pq.top();
pq.pop();
}
ans=max(ans,sum);
}
查看5道真题和解析