【
这题显然是个贪心，然而我们应该如何贪才能得到最优解==。。。。
假设我们按重量升序贪心，那我们可以得到反例（假设在挂缀底部）：设有
那么当
假设我们按拉力升序贪心，依旧可以得到反例（假设在挂缀顶部，，
那么当
==O(n logn)code：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; struct hq{long long wgt,f,sum;bool operator <(hq const &a) const{return sum<a.sum;} }a[1000001]; int n; long long nowwgt=0,nowl=0; priority_queue<int> q; int main() {int i;scanf("%d",&n);for (i=1;i<=n;++i){scanf("%I64d%I64d",&a[i].f,&a[i].wgt);a[i].sum=a[i].f+a[i].wgt;}sort(a+1,a+n+1);for (i=1;i<=n;++i){if (nowwgt<=a[i].f) {q.push(a[i].wgt); nowl++; nowwgt=nowwgt+a[i].wgt;}else if (q.top()>a[i].wgt) {nowwgt=nowwgt-q.top()+a[i].wgt; q.pop(); q.push(a[i].wgt);}}printf("%lld\n%lld\n",nowl,nowwgt); }
版权声明：本文为博主原创文章，未经博主允许不得转载。
人生重要的不是所站的位置，而是所朝的方向
