2020牛客寒假算法基础集训营2-F 拿物品

题目链接： https://ac.nowcoder.com/acm/contest/3003/F
一开始想法居然是放三个数组，一个原数组，一个按a排序，一个按b排序，毫无疑问T了；
看了题解，我们应该从反面思考，假设已经选完了，二者交换一个物品，那么二者所得都变小，可以得出二者都会倾向于选择a+b大的物品，所以按a+b贪心就可；
代码如下：

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>

#define lson  rt << 1
#define rson  rt << 1 | 1
#define il inline
#define ll long long
#define LL long long
using namespace std;
const int maxn = 2e5 + 10;
const ll inf = 0x7ffffffffff;
const ll mod = 1e9 + 7;

template<class T>
inline void read(T &res) {
    char c;
    T flag = 1;
    while ((c = getchar()) < '0' || c > '9')if (c == '-')flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')res = res * 10 + c - '0';
    res *= flag;
}

ll t;

ll qpow(ll a, ll b) {
    ll ans = 1;;
    a %= mod;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans % mod;
}
struct node{
    ll a,b,inv;
}x[maxn];
bool cmp(node &x,node &y){
    return x.a+x.b>y.a+y.b;
}
int main() {
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++){
        read(x[i].a);
        x[i].inv=i+1;
    }
    for(ll i=0;i<n;i++)read(x[i].b);
    sort(x,x+n,cmp);
    vector<int> p1,p2;
    ll cnt=0;
    while(cnt<n){
        p1.push_back(x[cnt++].inv);
        if(cnt==n)break;
        p2.push_back(x[cnt++].inv);
    }
    ll len1=p1.size(),len2=p2.size();
    for(ll i=0;i<len1;i++) cout<<p1[i]<<' ';cout<<endl;
    for(ll i=0;i<len2;i++) cout<<p2[i]<<' ';
    return 0;
}