Codeforces 798D

题目链接：http://codeforces.com/problemset/problem/798/D

题目大意：从长度为n的序列A和序列B中分别选出k个下表相同的数要求，设这两个序列中k个数和分别为ta,tb，两个序列总和分别为asum,bsum。要求ta*2>asum&&tb*2>bsum,k<=n/2+1.

解题思路：首先，肯定要选n/2+1的吧。我们把序列A当成第一层，序列B当成第二层。第一层：按从大到小严格排好。在第二层上：每两个取大的那一个，那最后的和肯定>=总和的一半，而且再加上第一个,所以所选数的和和>总和的一半。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+5;

struct node {
    int a;
    int b;
    int num;
}t[N];

bool cmp(node x,node y){
    return x.a>y.a;//第一层按从大到小排好
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i].a;
    }
    for(int i=1;i<=n;i++){
        cin>>t[i].b;
        t[i].num=i;
    }
    sort(t+1,t+1+n,cmp);
    cout<<n/2+1<<endl;
    cout<<t[1].num<<" ";
    for(int i=2;i<=n;i+=2){
        cout<<(t[i].b>t[i+1].b?t[i].num:t[i+1].num)<<" ";//两两取较大的那个 
    }
    cout<<endl;
    return 0;
} 

还有一种利用random_shuffle随机排列来写的,就是每次排好都选前k个，总会选到符合条件的答案,玄学。。。。：

#include<iostream>
#include<algorithm>
#include<cstdlib> 
#include<time.h>
using namespace std;
const int N=1e6+5;
typedef long long LL;
struct node {
    int a;
    int b;
    int num;
}t[N];

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    LL asum=0,bsum=0;
    for(int i=1;i<=n;i++){
        cin>>t[i].a;
        asum+=t[i].a;
    }
    for(int i=1;i<=n;i++){
        cin>>t[i].b;
        t[i].num=i;
        bsum+=t[i].b;
    }
    cout<<n/2+1<<endl;
    srand(time(NULL));
    while (1) {
        random_shuffle(t+1, t+n+1);
        LL ta=0,tb=0;
        for(int i=1;i<=n/2+1;i++){
            ta+=t[i].a;
            tb+=t[i].b;
        } 
        if (2*ta>asum&&2*tb>bsum) {
            for(int i=1;i<=n/2+1;i++){
                cout<<t[i].num<<" ";
            }
            cout<<endl;
            return 0;
        }
    }
    return 0;
}