Difference Array

发表于 分类于 ，

    你有一个初始长度为 $n$ 的有序数组 $a$（从小到大）。设 $a$ 当前长度为 $l$，你要对 $a$ 作差分，即令 $b_i = a_{i+1} - a_i(1\le i < l)$，然后将 $b$ 数组从小到大排序，接着让 $a_i = b_i(1 \le i < l)$，并继续执行上述操作。

    显然，每一次操作后 $a$ 数组的长度都会减少 $1$；执行 $n - 1$ 次操作之后，$a$ 中只会剩下一个元素，请你输出这个剩下的元素。

    输入包含多组数据，第一行一个正整数 $t(0 < t \le 10^4)$，表示数据组数。

    对于每一组数据：

    • 第一行一个正整数 $n(1 < n \le 10^5)$，表示 $a$ 数组的初始长度

    • 第二行 $n$ 个整数 $a_i(0 \le a_i \le 5\times10^5)$，表示 $a$ 数组。

Difference Array

Created by LXC on Mon Feb 26 11:44:55 2024

https://codeforces.com/problemset/problem/1707/B

ranting: 1900

tag: brute force, data structures, implementation, sortings

problem

你有一个初始长度为 $n$ 的有序数组 $a$（从小到大）。设 $a$ 当前长度为 $l$，你要对 $a$ 作差分，即令 $b_i = a_{i+1} - a_i(1\le i < l)$，然后将 $b$ 数组从小到大排序，接着让 $a_i = b_i(1 \le i < l)$，并继续执行上述操作。

显然，每一次操作后 $a$ 数组的长度都会减少 $1$；执行 $n - 1$ 次操作之后，$a$ 中只会剩下一个元素，请你输出这个剩下的元素。

输入包含多组数据，第一行一个正整数 $t(0 < t \le 10^4)$，表示数据组数。

对于每一组数据：

  • 第一行一个正整数 $n(1 < n \le 10^5)$，表示 $a$ 数组的初始长度

  • 第二行 $n$ 个整数 $a_i(0 \le a_i \le 5\times10^5)$，表示 $a$ 数组。

solution

对于值域在0到U的n个升序的数$a_1, \cdots a_n$，两两相邻的数作差，不同的数的个数最多有多少个？

不妨设$a_1 = 0, a_n = U$，$b_i = a_{i+1}-a_i$，显然$b_1+\cdots + b_{n-1} = U$，我们需要尽量让$b_i$不同，一种最理想的状态，$b_i$都不同，为了让b长度数量尽量大，可以最小化每个$b_i$,分别取$0,1,2,3,\cdots,t$，$t$是最后一个不同的数，我们知道$t(t+1)/2 = U$，因此最多只有$\sqrt U$个不同的数

我们知道相同的数作差为0,所以大多数重复的元素是0，额外记录0的数量，然后暴力迭代，由于U=5e5,只需要较少次迭代，数组大小将快速下降。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i:a) cin >> i;
    reverse(a.begin(), a.end());
    int z = 0;
    while (a.size() && a.back() == 0) a.pop_back(), z++;
    // cout << a << " " << z << endl;
    while (a.size() > 1) {
        vector<int> b;
        for (int i=1; i<a.size(); i++) {
            b.push_back(a[i-1]-a[i]);
        }
        if (z>0) {
            z--;
            b.push_back(a.back());
        }
        sort(b.rbegin(), b.rend());
        a = b;
        while (a.size() && a.back() == 0) a.pop_back(), z++;
        // cout << a << " " << z << endl;
    }
    // cout << "div ---- " << endl;
    cout << (a.size()?a[0]:0) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}