题意:

给两个长度为n的数组, 要求你找到(n+1)/2个下标,分别为p1, p2,p3....

要求: 图片说明

思路过程:

首先读完题大概可以看出来是贪心, 那么如何贪呢,贪心的话基本都要排序,尤其是这种求对总的贡献的题目,关键在于按什么排序,首先我想到的是按每个下标对的a[i]+b[i] 排序, 并且从大到小来sum1加上每个a[i]然后 sum2加上每个b[i] 当有sum1或者sum2 达标时候,如果是sum1达标, 则从当前位置开始重新排序,按照b[i]的大小重新排序, 反知。
结果wa8了 经过仔细思考后发现,我的想法只是勉强贪心,不够贪心, 必须特别贪心才可以。
于是我看了题解。。。。

这里介绍题解,并且写上我遇到的坑。

题解

  首先我们按照a[i]的大小排序,要记得记录下标与对应的b[i],从大到小排序,首先我们选择a[1],因为 要从n个数字里面选(n/2+1)个我们先把+1 选择了,这时候就把剩下的所有数字两个两个一组, 选择每组里面b[i]更大的那一个就可以了。

图片说明

这里我们观察图片加已理解,首先选择的要比一半多一个,然后选择的2 > sum 我们已经选择了a[1]与b[1] 那么 选择的2 >= sum 就可以了, 多了个等于,
然后我们看图片上面的a数组,选择了a[1] 之后分组无论选择哪一个都符合最后的和*2 大于suma, 这是为什么呢?
因为,a[1]一定大于a[2] 或者 a[3] , 比如我们选择了 1 3 5 7。。。。 1>2 3>4 5>6....
比如我们选择了 1 2 5 6 那么 1>3 2>4 5>6... 所以我们无论选择哪一个a都一定符合
对于数组b来说, 我们在两个中选择大的那一个一定符合。

坑:

主要就是超时问题,我第一步将cin 改为scanf 超时, 我将数组优化 还是超时, 改成快读还是超时,之后发现是重载运算符卡时间了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
ll n;
ll a[maxn], b[maxn];

struct Node
{
    ll a, b,pos;
    bool operator < (Node &p1)
    {
        return p1.a < a;
    }
}t[maxn];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch =='-')flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; i ++) t[i].a = read();
    for(int i = 1; i <= n; i ++) t[i].b = read(), t[i].pos = i;
    sort(t+1, t+1+n);    
    printf("%d\n",n/2+1);
    printf("%lld ",t[1].pos);
    for(int i = 2; i <= n; i += 2)
    {
        if(t[i].b > t[i+1].b)
            printf("%lld ",t[i].pos);
        else
            printf("%lld ", t[i+1].pos);
    }
    return 0;
}