P8976 「DTOI-4」排列题解

是青白呀 · 2023-02-01 19:18:26 · 题解

P8976 「DTOI-4」排列

update 2023/2/2 添加了一个例子便于理解

题目描述

给你一个偶数 n 和两个整数 a, b，请你构造一个长为 n 的排列 p，使得其满足 \displaystyle\sum_{i = 1}^{\frac{n}{2}} p_i \geq a 且 \displaystyle\sum_{i = \frac{n}{2} + 1}^{n} p_i \geq b。无解则输出 -1。

思路分析

要将长度为 n 的排列分为两部分，分别满足两个不小于某个值的条件，则在考虑其中一个条件时，一定要尽可能使另一个条件能被得到满足。

在本题中，在考虑区间 \left[1,\frac{n}{2} \right] 时，要使该区间和等于 a，才能使后半部分区间和大于等于 b 的条件尽可能被满足。于是考虑如何选取 \frac{n}{2} 个数使得其和为 a。首先我们容易知道，可以使得和为 a 的条件为 a \in \left[\frac{n(1+\frac{n}{2})}{4},\frac{n(\frac{n+1}{2}+n)}{4} \right]，其中左右边界分别对应取 \left[1,\frac{n}{2} \right] 的所有数和取 \left[\frac{n+1}{2},n \right] 的所有数的情况。考虑先选 \left[1,\frac{n}{2} \right] ，此时 sum=\frac{n(1+\frac{n}{2})}{4}。考虑将已选择的数替换为更大的数。为了避免替换时发生重复，每一次将已选中的 \left[1,\frac{n}{2} \right] 中最大的数 maxn 替换为 maxn+\frac{n}{2}，则每替换一次，sum 的值增加 \frac{n}{2}。则我们共需操作 \lfloor \frac{a-sum}{\frac{n}{2}} \rfloor 次，并将下一个 maxn 替换为 maxn+(a-sum) \mod \frac{n}{2} 的值。这样可以保证所选择的数不重复。最后再判断剩余数的和是否满足大于等于 b 即可。

为了便于理解，这里举一个例子。

1
8 23 13

一开始我们选中的是这些数：

1 2 3 4

此时 sum=10，太小了，与目标 a=23 的差值为 13。接下来进行上述替换操作。

1 2 3 8
1 2 7 8
1 6 7 8

此时的 sum 为 22。到此，我们共操作了 \lfloor \frac{a-sum}{\frac{n}{2}} \rfloor 次，即 3 次，每一次都让 sum 的值增加了 4。若再操作一次使 1 变成 5，sum 的值就会超过 a，不满足我们的贪心策略，进而使后四个数不小于 b 的要求无法满足。所以我们将最后一个 maxn 替换为 maxn+(a-sum) \mod \frac{n}{2}，使得 sum=a。代入数据发现，在这里我们应将 1 替换为 2。则最后的序列为：

2 6 7 8 1 3 4 5

恰好满足条件。

这里需要注意，a<\frac{n(1+\frac{n}{2})}{4} 不意味着无解，在这种情况下直接判断 b 与 \frac{n(\frac{n+1}{2}+n)}{4} 的关系即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int t;
signed main(){
    int t;
    read(t);
    while(t--){
        int n,a,b;
        read(n),read(a),read(b);
        int sum=(1+n/2)*n/4;
        if(sum>=a){//a选择1~n/2
            if((1+n)*n/2-sum<b)printf("-1\n");
            else{
                for(int i=1;i<=n;i++)
                    printf("%d ",i);
                printf("\n");
            }
            continue;
        }
        int movnum=(a-sum)/(n/2);//增加n/2的次数
        if(movnum>n/2||(movnum==n/2&&(a-sum)%(n/2))){//总操作次数不能大于n/2
            printf("-1\n");
            continue;
        }
        bool vis[N]={};//标记哪些数属于前半部分
        int suma=0;
        for(int i=1;i<(n/2)-movnum;i++)
            suma+=i,vis[i]=1;
        suma+=(n/2)-movnum+(a-sum)%(n/2);
        vis[(n/2)-movnum+(a-sum)%(n/2)]=1;
        for(int i=(n/2)-movnum+1;i<=n/2;i++)
            suma+=i+n/2,vis[i+n/2]=1;
        if((1+n)*n/2-suma<b)printf("-1\n");
        else{
            for(int i=1;i<=n;i++)
                if(vis[i])printf("%d ",i);
            for(int i=1;i<=n;i++)
                if(!vis[i])printf("%d ",i);
            printf("\n");
        }
    }
    return 0;
}

P8976 「DTOI-4」排列 题解