题意(搬运于洛谷):
题意:给两个长度为n的数列A,B,要求至多选择n/2+1个下标,使得A数组中选出的数的和的两倍大于sumA,B数组中选出的数的和的两倍大于sumB
题解:
题目说选择n/2+1这些数,+1这个数可能是突破点,但是太菜了,想了好久都没想出来怎么做。
看了一眼题解。
可以先把这串序列按照a的大小排个序,这样之后我们先选出A[0]这一组来。
后面的序列两两分为一组。
由于是按照A序列排的序,可以保证



这样选择后面B中较大那个元素,可以同时保证A中也成立。

代码:

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include
#define endl '\n'
#define int long long
using namespace std;
const int maxn=1e5+10;

struct node{
    int a,b,id;
}a[maxn];

struct rule{
    bool operator ()(const node & a,const node & b){
    return a.a>b.a;
    }
};

signed main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i>a[i].a,a[i].id=i;
    for(int i=1;i>a[i].b;
    sort(a+1,a+n+1,rule());
    vector ans;
    ans.push_back(a[1].id);
    for(int i=2;i<=n;i+=2){
        if(i==n) ans.push_back(a[i].id);
        else{
            if(a[i].b>a[i+1].b) ans.push_back(a[i].id);
            else ans.push_back(a[i+1].id);
        }
    }
    cout<<ans.size()<<endl;
    for(auto i:ans) cout<<i<<" ";
    return 0;
}