P8278 题解

SSqwq_ · 2022-04-13 10:31:33 · 题解

题意

给定元素个数为 n 的 a 数组的前缀和数组 p ， p 数组的一部分被隐去（题目体现为 -1 ），要求复现任意符合要求的 a 数组，且对于任意 1 \leq i \leq n ， a_i 不得大于 1000 。

思路

思路1：50 分

相信与许多人的思路一样，遍历 p 数组，遇见 p_i 不是 -1 ，就将 i 之前的方案输出出来。为了保证分配的数都是整数，将分配区间内的前 i-1 个数全部设为 1 ，而第 i 个数自然就是 p_i-(i-1) 。

但是，这个做法被毙掉了。

思路2：100 分

大家注意看一下题意中被我加粗的那句话。

且对于任意 1 \leq i \leq n ， a_i 不得大于 1000

若构造数据使得 p_1=p_2=-1 ，p_3=10000 ，显而易见的，50 分思路构造的 a 数组的第 3 项将会是 9998 ，不符合题意。

因此，我们做到尽量平摊，使用整除的方式将 p_i 平均分配到整个分配区间中。注意若 p 数组的末尾有若干个 -1 ，则一律输出 1 。

于是下面的AC代码就呼之欲出了。

#include<bits/stdc++.h>
using namespace std;
int p[100001];
int main()
{
    register int t;
    scanf("%d",&t);
    while(t--)
    {
        register int n;
        register int mult=0;
        register int chuli=0;
        scanf("%d",&n);
        for(register int i=1;i<=n;i++)scanf("%d",&p[i]);
        for(register int i=1;i<=n;i++)
        {
            mult++; //变量mult用于记录分配区间长度
            if(p[i]!=-1)
            {   
                p[i]-=chuli;
                chuli+=p[i];
                register int tmp=p[i];
                for(register int j=0;j<mult-1;j++)
                {
                    printf("%d ",p[i]/mult); //将p[i]平摊到分配区间中
                    tmp-=p[i]/mult;
                }
                printf("%d ",tmp);
                mult=0;
            }
        }
        for(register int j=0;j<mult;j++)
        {
            printf("1 ");  //p数组末尾仍有-1，一律输出1
        }
    }
    return 0;
}