uoj21 缩进优化（整除分块，乱搞）

题目大意：

给定一个长度为$n$的序列

让你找一个$x$，使得$ans$尽可能小

其中$$ans=\sum_{i=1}^{n}\lfloor\frac{a_i}{x}\rfloor + \sum_{i=1}^{n} a_i\mod x $$

我们看到这个式子，可以考虑化简一下$$ans=\sum_{i=1}^{n}\lfloor\frac{a_i}{x}\rfloor + \sum_{i=1}^{n} a_i-\lfloor\frac{a_i}{x}\rfloor \times x $$

然后再合并一下下

\[ans=\sum_{i=1}^{n} a_i + \sum_{i=1}^{n} \lfloor\frac{a_i}{x}\rfloor \times (1-x)
\]

然后我们就可以枚举$x$和枚举$\lfloor\frac{a_i}{x}\rfloor$

虽然我也不知道为什么复杂度是对的

不过貌似就是过了哎

记得用桶维护一下$a_i$的值，然后暴力算即可

直接上代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

inline long long read()

{

   long long x=0,f=1;char ch=getchar();

   while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}

   while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

   return x*f;

}

const int maxn = 2e6+1e2;

long long  sum[maxn];

int n,m;

long long a[maxn];

long long max1;

long long ans=1e18;

long long tmp;

int main()

{

  scanf("%d",&n);

  for (int i=1;i<=n;i++) a[i]=read(),sum[a[i]]++,max1=max(max1,a[i]),tmp=tmp+a[i];

  for (int i=1;i<=max1;i++) sum[i]+=sum[i-1];

  for (long long x=1;x<=max1;x++)

  {

  	  long long cnt=0;

  	  for (long long i=0;i<=max1/x;i++)

  	  {

  	  	long long l = x*i;

  	  	long long r = min(x*(i+1)-1,max1);

  	  	cnt+=(1-x)*(sum[r]-sum[l-1])*i;

  	  }

  	  ans=min(ans,cnt);

  }

  ans=tmp+ans;

  cout<<ans;

  return 0;

}

巴特西

uoj21 缩进优化（整除分块，乱搞）

最新文章

热门文章