打卡信奥刷题（3395）用C++实现信奥题 P9936 [NFLSPC #6] 等差数列

P9936 [NFLSPC #6] 等差数列

题目背景

题目描述

Alek 岁在某知名 OJ 代码力量上做了 $a_i$ 道难度为 $i$ 的题。他希望做一些题使得 $a_i$ 形成 公差非正 的等差数列，这样画出来的统计图表很好看。

尽管 Alek 岁一天能做 42 道题，但他依然希望做尽可能少的题达到目标。你需要求出新做题数的最小值。

你可以认为 OJ 上有足够多的各种难度的题目。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

• 第一行一个整数 $n$ 表示难度总数。
• 第二行 $n$ 个整数 $a_i$。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

6
2
822 1064
2
1064 822
4
1 3 4 2
4
2 4 3 1
6
2 6 2 1 4 4
9
9 9 8 2 4 4 3 5 3

输出 #1

242
0
6
4
17
25

说明/提示

对于所有数据，$1\le T\le 100$，$1\le n,\sum n\le 10^5$，$1\le a_i\le 10^9$。

• 子任务 1（$30$ 分）：$\sum n\le 10^3$。
• 子任务 2（$70$ 分）：无特殊限制。

Source：NFLSPC #6 L by Alex_Wei

C++实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
int a[N], n, T;
int f(int d) {
int mx = 0;
for (int i = 1; i <= n; ++i) {
int cur = a[i] + (i – 1) * d;
if (cur > mx) mx = cur;
}
int sum = 0;
for (int i = 1; i <= n; ++i) {
sum += mx – (i – 1) * d – a[i];
}
return sum;
}
signed main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> T;
while (T—) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
int l = 0, r = 1e9;
while (r – l > 3) {
int m1 = l + (r – l) / 3;
int m2 = r – (r – l) / 3;
if (f(m1) < f(m2)) r = m2;
else l = m1;
}
int ans = 1e18;
for (int i = l; i <= r; ++i) ans = min(ans, f(i));
cout << ans << '\\n';
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容