文档网站超链接怎么做,潘家园做网站公司,网站建设服务费用,我有虚拟服务器怎么快速做网站正题 题目大意
一个长度为nnn的序列。可以选择一段区间旋转#xff0c;求使得∑i1n[aii]\sum_{i1}^n[a_ii]∑i1n[aii]最大。 解题思路
现在序列中每隔一个插入一个#\##号(伪插入) 用gig_{i}gi表示以中点为iii的序列翻转后能够对应的数字。
然后枚举中心点#xff0c…正题 题目大意
一个长度为nnn的序列。可以选择一段区间旋转求使得∑i1n[aii]\sum_{i1}^n[a_ii]∑i1n[aii]最大。 解题思路
现在序列中每隔一个插入一个#\##号(伪插入) 用gig_{i}gi表示以中点为iii的序列翻转后能够对应的数字。
然后枚举中心点然后从短到长枚举翻转可以对应的数组然后统计答案。 codecodecode
#includecstdio
#includealgorithm
#includecstring
#includevector
using namespace std;
const int N500010;
int n,a[N],s[N],ans;
vectorint g[N];
int main()
{freopen(rotate.in,r,stdin);freopen(rotate.out,w,stdout);scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);g[ia[i]].push_back(abs(a[i]-i));s[i]s[i-1](a[i]i);}for(int i1;i2*n;i)if(!g[i].empty()){sort(g[i].begin(),g[i].end());int kg[i].size();for(int j0;jk;j){int l(i-g[i][j])/2,r(ig[i][j])/2;ansmax(ans,s[n]-s[r]s[l-1]j1);}}printf(%d,ans);
}
