原题
思路概述
题意分析
给定一个长度为 \(n\) 的序列 \(\{a\}\)。每次执行以下操作
对序列 \(\{a\}\) 进行差分，得到差分序列 \(b_i=a_{i+1}-a_i(1≤i<n)\)。
将差分序列 \(\{b\}\) 进行升序排序。
将差分序列中的数值按顺序赋回原序列。
求 \((n-1)\) 次操作后最后剩下的数字
思路分析
先考虑暴力模拟，则时间开销 \(O(n)\) 的差分与时间开销 \(O(n\log n)\) 的排序需要进行 \(n\) 次，总时间复杂度 \(O(n^2\log n)\)。明显超时。
手动模拟几组数据不难发现，对于出现的绝大部分序列，在差分、排序、赋值的过程中总会在最后出现一串 \(0\)。通过进一步分析与模拟可以发现，去除出现的绝大部分 \(0\) 不会影响最后的结果，反而可以节省若干次计算。
考虑每次差分后将序列中的 \(0\) 去除后再排序，可以将时间复杂度降至题目要求范围内。
算法实现
关于时间复杂度的证明
我们先列出一组差分序列全为 \(0\) 的序列，即序列的所有元素都相等。例如以下序列：
\[\{1,1,1,1,1,1\} \]通过简单数学分析可以知道，该数列在上一次操作前必定是一阶等差数列（为方便表述，笔者称其为逆操作），且元素数量比上述数列多 \(1\)。如下：
\[\{1,2,3,4,5,6,7\} \]以此类推，可以知道再上一次操作前的序列必定是二阶等差数列。即对初始序列 \(\{1,1,1,1,1,1\}\) 进行 \(n\) 次逆操作后得到的原始序列是 \(n\) 阶等差数列。
通过不完全归纳可以得到基于以上序列推出的 \(n\) 阶等差数列第 \(n\) 项为 \(2^n\)。相应地，对于长度为最大数为 \(2^n\) 的 \(n\) 阶等差数列，只需要 \(n\) 次操作，就可以将其变为 \(1\)。这就确立了最终时间复杂度与 \(\log \max\{a_i\}\) 的关系。
根据题目给出 \(0≤a_i≤5×10^5\) 的数据范围可以知道，即使是最大的 \(a_i\) ，在去除前导 \(0\) 的情况下，也可以理论时间复杂度 \(O(n\log(n+\max\{a_i\})\) 下通过数据点。
关于前导 \(0\)
对于前导 \(0\)，如果全部去除，则必然出现问题。例如以下数据：
\[\{0,0,0,7,9\} \]手动模拟结果为 \(1\)，但若去除所有前导 \(0\)，结果则为 \(2\)。
若保留一个前导 \(0\)，结果为 \(5\)，仍然与模拟结果不符。
由上述样例的分析可知，若序列中存在一串长度为 \(m\) 的由非零数组成的子序列，其前方有 \(k(k≥m)\) 个前导 \(0\)，则其中的 \(m\) 个前导 \(0\) 对差分都是有贡献的。所以对于这些前导 \(0\) 的贡献，需要用一个变量来记录。而对于一个前面存在有贡献前导 \(0\) 的非零子序列，则在赋值时在差分序列中预置原序列第一个数，就可以在下次差分前插入前导 \(0\)。
AC code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<set>
#include<ctime>
#define RI register int
#define RB register bool
using namespace std;
const int maxn=1e5+10;
int T,n,cnt;
int a[maxn],b[maxn];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
for(cin >> T,cnt=0;T;--T,cnt=0)
{
cin >> n;
for(RI i=1;i<=n;++i)
{
cin >> a[i];
if(!a[i])
{
++cnt;
--i;--n;
}
}
for(RI pos=0;n>1;pos=0)
{
if(cnt)
{
b[++pos]=a[1];
--cnt;
}
for(RI i=1;i<n;++i)
if(a[i+1]-a[i]) b[++pos]=a[i+1]-a[i];
else ++cnt;
n=pos;sort(b+1,b+n+1);
for(RI i=1;i<=n;++i) a[i]=b[i];
}
printf("%d\n",a[n]);
}
return 0;
}