阅读量:0
L-知
题意：给定一组数组，每次操作可以选择一个ai变成ai+1，a（i+1）=a（i+1）-1，可以无限次操作。求数组最大乘积。
分析：对于每个ai计算【i，i】，【i，i+1】，。。。【i，n】的平均值的最大值s，将ai减去s即可
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; void sol(){ int n;cin>>n;ll a[n+10],sum[n+10]; for(int i=1;i<=n;i++){ cin>>a[i]; } sum[0]=0; for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; } for(int i=1;i<n;i++){ ll s=0; for(int j=i+1;j<=n;j++){ s=max(s,(sum[j]-sum[i]+a[i])/(j-i+1)); } if(a[i]<s){ s-=a[i]; a[i]+=s; a[i+1]-=s; } } ll ans=1; for(int i=1;i<=n;i++){ ans=ans*a[i]; ans%=mod; } cout<<ans<<endl; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int t;cin>>t; while(t--)sol(); return 0; } 