给定长度为n的递增数组a,进行n - 1次操作:求当前a数组的差分数组,然后使a为差分数组,继续进行操作。求最后数组的元素是什么
题目
思路:
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
#define pb push_back
#define lson p << 1
#define rson p << 1 | 1
#define fi first
#define se second
const int maxn = 1e6 + 5, maxm = 5e3 + 5, mod = 1e9 + 7;
int a[maxn], b[maxn], pos[maxn];
int n, m;
string s;
int d[maxn], pre[maxn], sum, q;void solve()
{int k;int res = 0;// int q;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];}for(int i = n - 1; i >= 1; i--){bool flag = 0;int last = a[i + 1];for(int j = i; j >= 1; j--){if(a[j] == 0) flag = 1;int tmp = last;last = a[j];a[j] = tmp - a[j];if(flag){sort(a + j, a + i + 1);break;}}if(!flag){sort(a + 1, a + i + 1);}}cout << a[1] << '\n';
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);int T = 1;cin >> T;// for(int i = 1; i <= T; i++){// num = i;// solve();// }while (T--){solve();}
}