(未完待续)
题目链接:GMOJ 6288。
题目
给定一个长度为 $n$ 的序列,你可以选择翻转一个任意正整数长度的区间,求翻转后最大的 $\sum _ {i=1}^n[a _ i=i]$。
题解
思路
代码
#include<cstdio>
#include<algorithm>
using std::max;
using std::pair;
using std::make_pair;
const int MAXN=100000+5;
int n;
int sum[MAXN];
pair<int,int> point[MAXN];
int main(void){
freopen("rotate.in","r",stdin);
freopen("rotate.out","w",stdout);
register int i,l,r,temp,ans=0;
scanf("%d",&n);
for(i=1;i<=n;++i){
static int x;
scanf("%d",&x);
point[i]=make_pair(x+i,max(x,i)-(x+i)/2);
sum[i]=sum[i-1]+(i==x);
}
sort(point+1,point+n+1);
for(i=1,temp=0;i<=n;++i){
l=point[i].first/2-point[i].second;
r=point[i].first-l;
temp=point[i].first==point[i-1].first?temp+1:1;
if(point[i].second)
ans=max(ans,sum[l-1]-sum[r-1]+temp);
}
printf("%d\n",ans+sum[n]);
return 0;
}
Excellent write-up. I definitely appreciate this website.
Thanks!