本文共 2489 字，大约阅读时间需要 8 分钟。

$$\mathrm{最佳解答}$$

题目链接： /

题目

输入

输出

样例输入

3588

样例输出

6

样例数据

TAB 的长度为 $4$ 的时候，答案是 $1+(5-4)+2+(8-8)+2+(8-8)=6$

数据范围

大数据

思路

这道题是一道数学题，不过可以用三分来做。

我这里讲数学方法，三分的博客等我们这里有人做出来，我把链接贴在这里。

我就化公式：（这里的除号都是整除， $min()$ 就是枚举 $x$ 然后统计最小值）

（不太会写公式，见谅） $min(\sum _{i=1}^n((a_i/x)+(a_i\%x)))$ $min(\sum _{i=1}^n((a_i/x)+(a_i-a_i/x\times x)))$ $min(\sum _{i=1}^n(a_i/x+a_i-a_i/x\times x))$ $min(\sum _{i=1}^n(a_i-a_i/x\times (x-1)))$ $min(\sum _{i=1}^n{a}_i-\sum _{i=1}^n(a_i/x\times (x-1)))$ $min(\sum _{i=1}^n{a}_i-\sum _{i=1}^n(a_i/x)\times (x-1))$

$\sum _{i=1}^n{a}_i$ 可以预处理，但是 $\sum _{i=1}^n(a_i/x)$ 怎么办呢？

我们有一种方法： 我们预处理出大于等于 $i$ 的数有多少个，我这里用 $b[i]$ 来存。 然后我们枚举当前枚举的 $x$ 的倍数，看有多少个数超过了 $x$ 的这个倍数，加进一个数组里面。最后这个数组里面存的数就是答案了。 为什么呢？ 因为我们可以发现，如果 $a/x=b$ ，那它其实就对答案贡献了 $b$ 次，那其实就是答案咯。

代码

#include
   
    #include
    
     #include
     
      #define ll long long#define rr registerusing namespace std;ll n, a[1000001], xr, sum, ans, tmp[1];ll b[1000001];ll read() {   //快读	ll an = 0, zhengfu = 1;	char c = getchar();	while (c < '0' || c > '9') {   		if (c == '-') zhengfu = -zhengfu;		c = getchar();	}	while (c >= '0' && c <= '9') {   		an = an * 10 + c - '0';		c = getchar();	}	return an * zhengfu;}int main() {   //	freopen("text.txt", "r", stdin);		memset(tmp, 0x7f, sizeof(tmp));//初始化	ans = tmp[0];		n = read();//读入	for (rr ll i = 1; i <= n; i++) {   		a[i] = read();//读入		sum += a[i];//求出a[i]的和		b[a[i]]++;//记录		xr = max(xr, a[i]);//求出最大值	}		for (rr ll i = xr - 1; i >= 1; i--)//求出有多少个大于i的数，用b[i]储存		b[i] += b[i + 1];		for (rr ll i = 1; i <= xr; i++) {   //枚举x		ll now = sum;		ll minus = 0;		for (rr ll j = i; j <= xr; j += i)//算公式			minus = minus + b[j];		now -= minus * (i - 1);		ans = min(ans, now);//找到答案最小的那个	}		printf("%lld", ans);//输出		return 0;}
     
    
   

转载地址：http://ozvh.baihongyu.com/