110. 数蝌蚪

SmallY

就是拟合一条y=kx+b的曲线,其中k题目已给出,所以对数据进行旋转变化,变成拟合一条y=b的直线,那么结果显然

n, k = map(int, input().split())
L = [int(i) for i in input().split()]
for i in range(n):
    L[i] -= k*i
L.sort()
if n%2:
    target = L[n//2]
else:
    target = (L[n//2]+L[n//2-1])//2
if target < 0:
    target = 0
res = 0
for i in range(n):
    res += abs(L[i]-target)
print(res)
Deuchie

用二分做的(卑微)

尝试合并一些行以使得我的代码离大佬的长度更近一点(迫真)

#include <array>
#include <cstdint>
#include <iostream>
array<uint32_t, 300001> tadpoles;
int main() {
    uint32_t n, k; std::cin >> n >> k;
    for (uint32_t i = 0; i < n; ++i)
        std::cin >> tadpoles[i];
    uint32_t lo = 0, hi = 10001;
    while (lo != hi) {
        uint32_t mid = lo + (hi - lo) / 2, standard = mid;
                uint32_t lower = 0, higher = 0, exact = 0;
        for (uint32_t i = 0; i < n; ++i, standard += k)
            if (tadpoles[i] == standard)
                ++exact;
            else if (tadpoles[i] < standard)
                ++lower;
            else
                ++higher;
        if (exact + higher < lower) {
            hi = mid;
        } else if (exact + lower < higher) {
            lo = mid + 1;
        } else {
            lo = hi = mid;
            break;
        }
    }
    uint64_t cost = 0;
    auto standard = lo;
    for (u32 i = 0; i < n; ++i, standard += k)
        if (tadpoles[i] < standard)
            cost += standard - tadpoles[i];
        else
            cost += tadpoles[i] - standard;
    std::cout << cost << '\n';
}
HongRed

最简单的思路, 先设目标数列的第一个元素为0, 然后看看这样的目标数列需要输入的数列的每个元素拿出或放入多少次. 然后根据这个进行优化.
优化思路是: 如果需要拿出的元素比不动和放入的还多, 则总可以把目标数列的所有元素加一, 让操作总数变小, 反之则不行(不能有负数). 怎么一次性判断需要拿出的元素总数比不动加放入的元素总数的相对大小, 以及优化多少呢? 维护每个元素要执行的操作的数组, 看看中位数就行.
示例代码:

#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;


long long sub[300001];
int main()
{
#ifdef debug
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    int n, k, b;
    long long result = 0, a = 0;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &b);
        sub[i] = b - a;
        a += k;
    }
    sort(sub, sub + n);
    if(sub[n/2] <= 0)
    {
        int temp = sub[n/2];
        for(int i = 0; i < n; i++) sub[i] += temp;
    }
    for(int i = 0; i < n; i++) result += sub[i];
    printf("%lld\n", result);
    return 0;
}
Cuibaby

include

include

using namespace std;
int main() {
long long n,k;
cin>>n>>k;
long long b[n];
long long sum=0,a,p;
for(int i = 0; i < n; i++) {
cin>>a;
b[i]=a-ik;
}
sort(b,b+n);
long long mid;
if(n&1)
mid=b[n/2];
else
mid=(b[n/2]+b[n/2-1])/2;
if(mid<0)
mid=0;
// for(int i =0; i < n; i++) {
// cin>>a;
// if(i==0)
// p=a;
// b[i]=i
k+p-a;//
// }
// sort(b,b+n);
// long long mid;
// if(b[n/2]<p) {
// mid=b[n/2];
// } else {
// mid=p;
// }
for(int i =0; i < n; i++) {
sum+=abs(b[i]-mid);
}
cout<<sum<<endl;
return 0;
}

你当前正在回复 博客/题目
存在问题!