P1675题解报告

Jason0211 · 2023-08-15 19:44:31 · 题解

看到标签里有随机化，乱写了一下直接过了。

这里提供一种随机化乱搞的做法：

首先，将数列从小到大将原序列排序，由于我们只需要使两组数的和尽可能大，根据贪心，我们可以将最小的 k 个分为一组，才能保证其他两组尽可能大（这里想一想就能明白了，无需证明）。

然后，对后面 2k 个数进行随机化排列，然后直接判断是否符合要求，不符合则继续，符合则直接输出。这里，我们可以选择使用 \operatorname{shuffle} 函数对原序列进行随机化打乱，实测出解率很高，每个测试点均可跑到 4 毫秒以内。

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int sum,id;
}a[185];
bool cmp(Node a,Node b)
{
    return a.sum<b.sum;
}
inline int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch)) {ch = getchar(); if (ch == '-') f =-1;}
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

int main()
{
    int k;
    k=read();
    int len=3*k;
    for(int i=1;i<=len;i++)
    {
        a[i].sum=read();
        a[i].id=i;
    }
    sort(a+1,a+len+1,cmp);
    for(int i=1;i<=k;i++)
    {
        printf("%d\n",a[i].id);
    }
    while(true)
    {
        random_shuffle(a+k+2,a+len+1);
        int ans=0,cnt=0,re=500*k;
        for(int i=k+1;i<=2*k;i++)
        {
            ans+=a[i].sum;
            if(ans>re)
            {
                cnt++;
                break;
            }
        }
        ans=0;
        for(int i=2*k+1;i<=len;i++)
        {
            ans+=a[i].sum;
            if(ans>re)
            {
                cnt++;
                break;
            }
        }
        if(cnt==2)
        {
            for(int i=k+1;i<=len;i++)
            {
                printf("%d\n",a[i].id);
            }
            break;
        }
    }
    return 0;
}