最佳解答

$Description$

TYB是一位热爱刷最佳解答的OI选手。
但是他很快就发现，他并不是一个常数小的选手，也不是一个会卡空间的选手。
那么一个常数和空间都大的选手如何才可以在最佳解答的排行榜上留下自己的名字呢？
那当然是通过代码长度啦！
但是有一天，他忽然发现，虽然自己的代码很短，但是实际代码量却很大。
原来他每一行代码的前面都有大量的空格，而大量的空格让代码量随之增大。
聪明的TYB决定要用TAB来解决这个问题。
具体来说，TYB决定给自己的TAB设定一个默认宽度x，然后对于他的第 行代码，将前面的每 个空格换成一个
TAB，直到不足 个空格。
我们定义额外的代码长度，就是TAB的个数加空格个数。
现在TYB想知道，他的最小额外代码长度是多少。

$Input$

第一行一个整数n，表示一共有n行代码
接下来 行，每行一个整数 ，表示这一行前面有多少个空格

$Output$

一行一个整数，表示最终的最小额外代码长度

$Sample$ $Input$

3
5
8
8

$Sample$ $Output$

6

$Hint$

TAB的长度为4的时候，答案是1+(5-4)+2+(8-8)+2+(8-8)=6
本题采用subtask进行测试
对于20%的测试点，满足 n < = 1 0 3 , a [ i ] < = 2000 n <= 10^3,a[i]<=2000 n<=103,a[i]<=2000
对于40%的测试点，满足 n < = 1 0 5 , a [ i ] < = 2000 n <= 10^5,a[i]<=2000 n<=105,a[i]<=2000
对于70%的测试点，满足 n < = 1 0 5 , a [ i ] < = 5000 n <= 10^5,a[i]<=5000 n<=105,a[i]<=5000
对于100%的测试点，满足 n < = 1 0 6 , a [ i ] < = 6000 n <= 10^6,a[i]<=6000 n<=106,a[i]<=6000

$Train$ $of$ $Thought$

就是求

其实商和余都可以用前缀和维护

所以先枚举$Tab$，再枚举$n$（简化）

#include
#include 
#include
#include
#define ll long long
using namespace std;
ll Sum[2000005], Num[2000005];
ll Ans, n, k, Max;
int main()
{scanf("%lld", &n);for(int i = 1; i <= n; ++i){scanf("%lld", &k);Num[k]++, Sum[k] += k;Max = max(Max, k);}for(int i = 2; i <= 2 * Max; ++i)Num[i] += Num[i - 1], Sum[i] += Sum[i - 1];//Num为权值小于i的有多少个，Sum为权值小于i的权值和Ans = 1e9;for(int i = 1; i <= Max; i++){ll t = 0;for(int j = 0, h = 0; j <= Max; j += i, h++)//注意：j += i, 可以将j到j + i - 1整合一起算{ll l = (Num[j + i - 1] - Num[j - 1]);//为j到j + i - 1的有多少个ll r = (Sum[j + i - 1] - Sum[j - 1]);//为j到j + i - 1的总和t += l * h +  r - j * l;//l}Ans = min(Ans, t);}printf("%lld", Ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！