NC221785. dd爱整齐
描述
如
以此类推，其中
如
现在给你一个序列
对于每次修正，你可以选择一个位置
输入描述
第一行两个正整数n,k(1≤k≤n≤1000000),
第二行n个正整数描述序列c,对于序列中第i(1≤i≤n)个数c[i],满足1≤c[i]≤1000000000
输出描述
一个数，表示最小修正次数
示例1
输入:
5 2 5 2 3 1 4
输出:
8
说明:
改成[1,2,1,1,2]，最小修正次数为(5-1)+(2-2)+(3-1)+(1-1)+(4-2)=8NC221785. dd爱整齐
描述
输入描述
第一行两个正整数n,k(1≤k≤n≤1000000),
第二行n个正整数描述序列c,对于序列中第i(1≤i≤n)个数c[i],满足1≤c[i]≤1000000000
输出描述
一个数，表示最小修正次数
示例1
输入:
5 2 5 2 3 1 4
输出:
8
说明:
改成[1,2,1,1,2]，最小修正次数为(5-1)+(2-2)+(3-1)+(1-1)+(4-2)=8C++ 解法, 执行用时: 505ms, 内存消耗: 8260K, 提交时间: 2021-07-30 22:21:01
#include <iostream>
using namespace std;
typedef long long ll;
ll n,k,a[1000005],sum=0,low=1e10,big=0;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
low=min(low,a[i]);
}
for(int i=1;i<=k;i++){
int c=0;
ll low2=1e10;
for(int j=i;j<=n;j+=k+1){
low2=min(low2,a[j]);
c++;
}
big=max(big,c*(low2-low));
}
cout<<sum-n*low-big;
return 0;
}