拿物品题解报告
拿物品
http://www.nowcoder.com/questionTerminal/868cfb40d17344c89db303f9992fbf85
这道题其实很简单,不要被最优策略几个字迷惑住了。
重点在分差越大。
我们考虑,牛牛每取一件物品,会得到ai的属性,并且让牛可乐失去了bi的属性,所以牛牛实际上得到了ai+bi的属性,牛可乐的取法同理,因此,这题的思想就转变为贪心。
2个姓牛的都尽可能取走ai+bi最大的物品,以此减小差距
贴上蒟蒻代码:
#include<bits/stdc++.h> #define maxn 200010 using namespace std; int n; struct Node{ int posA,posB; }a[maxn]; struct New{ int key,pos; }b[maxn]; bool cmp(New x,New y){ return x.pos>y.pos; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i].posA); for(int i=1;i<=n;++i){ scanf("%d",&a[i].posB); b[i].pos=a[i].posA+a[i].posB; b[i].key=i; } sort(b+1,b+n+1,cmp); for(int i=1;i<=n;++i) if(i&1) printf("%d ",b[i].key); printf("\n"); for(int i=1;i<=n;++i) if(!(i&1)) printf("%d ",b[i].key); return 0; }