解题思路:直接在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 人评分
2^k进制数 (C++代码)使用递归方法浏览:722 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:586 |
简单的a+b (C语言代码)浏览:546 |
ASCII帮了大忙浏览:751 |
WU-输出正反三角形 (C++代码)浏览:1024 |
C语言程序设计教程(第三版)课后习题6.8 (C++代码)浏览:592 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:589 |
良心推荐——>题解1049:C语言程序设计教程(第三版)课后习题11.1 (C语言描述——简单明了,时间复杂度低)浏览:1293 |
杨辉三角 (C语言代码)浏览:681 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:622 |