L - Division into Teams 题解

算法 题解

题目大意

有n个人(2<=n<=500000)，每个人都有一个能力值ai(1<=ai<40000)，现在将这些人分为两队，一个组x个人，另一个组y个人。分队依据为：
x+y=n
|x-y|<=1
一个队的能力值pi和另一个队的能力值qi满足：

现在求一种分配方法。

分析

本题可以先将这些人的能力值进行排序，然后把第1，第n-1，第3，第n-3……个人分为一队，其他人分为另一队，需要注意的是，第一队的人的能力值的总和是相对较小的，如果n为奇数，需要将中间那个人分到第一队。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
    int n;
    struct boy
    {
        int ability;
        int index;
    };
    vector <boy> b;
    bool flag[100005]={false};
    int t1num=0;
bool comp(boy x,boy y)
{
    return x.ability<y.ability;
}
int main(void)
{
    cin>>n;
    int i,j;
    for(i=0;i<n;i++)
    {
        boy l;
        cin>>l.ability;
        l.index=i+1;
        b.push_back(l);
    }
    sort(b.begin(),b.end(),comp);
    int num=n%2==0?n/2:n/2+1;
    for(i=0;i<num;i++)
    {
        if(i%2==0)
            j=i;
        else
            j=n-i-1;
        flag[b[j].index]=true;
        t1num++;
    }
    cout<<t1num<<endl;
    for(i=1;i<=n;i++)
    {
        if(flag[i])
            cout<<i;
        if(i!=n&&flag[i])
            cout<<" ";
    }
    cout<<endl;
    cout<<n-t1num<<endl;
    for(i=1;i<=n;i++)
    {
        if(!flag[i])
            cout<<i;
        if(i!=n&&!flag[i])
            cout<<" ";
    }
    cout<<endl;
    return 0;
}