自动搬运

查看原文

来自洛谷，原作者为

	SSqwq_ 曾用名 Summer_Sheep | 主页有各类工具 | AFOed 24.11.30

搬运于2025-08-24 22:37:36，当前版本为作者最后更新于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;
}