解题思路:直接在a[i]上操作,没有好的解决办法,考虑一下前缀和,发现问题就转换成了:给定一个序列,重新排列元素顺序,要求s0,sn的位置不能变即固定起点终点 ,使得该序列的相邻两数之差的绝对值最小。 可以证明当该序列单调时,有相邻两数的差值的绝对值最小。
注意事项:
具体思路见:灵能传输 思路解析
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=3e5+3; ll a[N],s[N]; bool vis[N]; int n; int main(){ int T; scanf("%d",&T); while(T--){ memset(vis,0,sizeof(vis)); scanf("%d",&n); s[0]=0; for(int i=1;i<=n;++i){ scanf("%lld",&s[i]); s[i]+=s[i-1]; } ll s0=0,sn=s[n]; if(s0>sn) swap(s0,sn);//前小后大,为方便取数,可避免讨论取数时重复取的问题。 sort(s,s+n+1); int l=0,r=n; for(int i=lower_bound(s,s+n+1,s0)-s;i>=0;i-=2){ a[l++]=s[i],vis[i]=1; } for(int i=lower_bound(s,s+n+1,sn)-s;i<=n;i+=2){ a[r--]=s[i],vis[i]=1; } for(int i=0;i<=n;++i){ if(!vis[i]) a[l++]=s[i]; } ll res=0; for(int i=1;i<=n;++i) res=max(res,abs(a[i]-a[i-1])); printf("%lld\n",res); } return 0; }
0.0分
10 人评分
C语言训练-斐波纳契数列 (C语言代码)浏览:2811 |
汽水瓶 (C语言代码)浏览:698 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:584 |
A+B for Input-Output Practice (C++代码)浏览:605 |
这可能是一个假的冒泡法浏览:985 |
WU-蓝桥杯算法提高VIP-勾股数 (C++代码)浏览:1592 |
WU-格式化数据输出 (C++代码)浏览:1194 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:587 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:548 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:681 |