蓝桥杯每日一题2023.10.22

题目描述

灵能传输 - 蓝桥云课 (lanqiao )

题目分析

发现每一次的灵能传输都是对前缀和s[i - 1]和s[i]的一次交换 

我们发现只剩下s1没有相减，在这里我们可以添加一个为0的s0，使整个式子表示完整

故为求max(s[i], s[i - 1])的最小值（发现当s单调时可以成立）

由于s[0]和s[n]的位置不变，但是s[0]和s[n]不一定是最大值或者最小值

故可以进行一个贪心策略 

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5 + 10; ll n, s0, sn, a[N], s[N], ans[N]; bool st[N]; void solve() { memset(st, 0, sizeof st); cin >> n; s[0] = 0; for(int i = 1; i <= n; i ++)cin >> a[i]; for(int i = 1; i <= n; i ++)s[i] = s[i - 1] + a[i]; s0 = s[0]; sn = s[n]; if(s0 > sn)swap(s0, sn); sort(s, s + n + 1);//注意此处两边的数的范围 for(int i = 0; i <= n; i ++) { if(s[i] == s0) { s0 = i; break; } } for(int i = n; i >= 0; i --) { if(s[i] == sn) { sn = i; break; } } ll l = 0, r = n; for(int i = s0; i >= 0; i -= 2) { st[i] = true; ans[l ++] = s[i]; } for(int i = sn; i <= n; i += 2) { st[i] = true; ans[r --] = s[i]; } for(int i = 0; i <= n; i ++) { if(!st[i]) { ans[l ++] = s[i]; } } ll res = 0; for(int i = 1; i <= n; i ++) { res = max(res, abs(ans[i] - ans[i - 1]));// s[i] - s[i - 1] = a[i] } cout << res << '\n'; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --) { solve(); } return 0; }