首页 > 代码库 > UOJ#21【UR #1】缩进优化
UOJ#21【UR #1】缩进优化
传送门 http://uoj.ac/problem/21
枚举 （调和级数？）
$\sum_{i=1}^{n} (a_i / x + a_i \bmod x) =\sum a_i - (\sum_{i=1}^{n} a_i /x) * (x-1)$
看上去并没有一个很好的办法确定x的取值？
大概只能暴力枚举了。
枚举x的大小，如果用分块加速的方法统计解，复杂度是O(n)+O(n/2)+O(n/3)+O(n/4)+...
累积起来是O(nlogn)
嗯？好像是正解？
イミワカナイ
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=1000010; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int n,mx=0;16 int a[mxn],smm[mxn];17 LL sum=0;18 LL calc(int lim){19 LL res=0;20 int i,cnt,last=0;21 for(i=lim-1,cnt=0,last=0;i;last=i,i+=lim,cnt++){22 i=min(i,mx);23 res+=cnt*((LL)smm[i]-smm[last]);24 if(i==mx)break;25 }26 return res*(lim-1);27 }28 int main(){29 int i,j;30 n=read();31 for(i=1;i<=n;i++){32 a[i]=read();sum+=a[i];33 smm[a[i]]++;34 mx=(mx>a[i])?mx:a[i];35 }36 for(i=1;i<=mx;i++){37 smm[i]+=smm[i-1];38 }39 LL ans=0x3f3f3f3f3f3f3f;40 for(i=1;i<=mx;i++)41 ans=min(ans,sum-calc(i));42 printf("%lld\n",ans);43 return 0;44 }
UOJ#21【UR #1】缩进优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。