题目大意:
给你n个钩码,每个钩码有一个承受能力和重量,问最多可以挂多少个钩码,再上一问的条件下,钩码总重最小是多少 n<=200000
这题明显是贪心
于是我们要找一个贪心策略,我们先假设没有按任何方式排序,存在c[i]+w[i]>c[i+1]+w[i+1]
我们如果把i挂在i+1上的话,那么底下还可以承受的重量:min(c[i],c[i+1]-w[i])
反过来就是:min(c[i+1],c[i]-w[i+1]) 只要当c[i]-w[i+1]>c[i+1]-w[i]时就要把它反过来
于是我们就按c[i]+w[i]排序,之后再用堆,能挂就挂
#include<queue> #include<cstdio> #include<iostream> #include<algorithm> typedef long long LL; const int maxn=200010; using namespace std; inline int getLL(){ char ch=getchar(); LL tmp=0; while (ch<'0' || ch>'9') ch=getchar(); for (;ch<='9' && ch>='0';ch=getchar()) tmp=tmp*10+ch-'0'; return tmp; } struct zy{ LL c,w; }a[maxn]; inline bool cmp(zy a,zy b){ return a.c+a.w<b.c+b.w; } priority_queue<int>q; LL n; int main(){ n=getLL(); for (int i=1;i<=n;++i){ a[i].c=getLL(); a[i].w=getLL(); } sort(a+1,a+n+1,cmp); LL sum=0; LL ans=0; for (int i=1;i<=n;++i){ if (sum<=a[i].c){ q.push(a[i].w); sum+=a[i].w; ans++; } else if (sum-q.top()<=a[i].c && q.top()>a[i].w){ sum+=a[i].w-q.top(); q.pop(); q.push(a[i].w); } } cout<<ans<<'\n'<<sum<<endl; }