哈理工第十届程序设计竞赛 B 减成一 题解

题目大意

给你一些数字，你可以进行一种操作，令一个区间的数字减少1，问令这些数字全为1的最小操作数。

解题思路

这题刚刚开始看的时候完全没思路。

后面感谢大佬抬我一手。

这就是一道纯差分题。

（我感觉自己都不会差分。。跟没学过一样。

上次比赛也是一道差分题卡了我好久。

对这一串数字进行构造差分数组。

由题意得，这种操作可以变成在差分数组中选取一位减1，一位加1。

而最终的数组应该除了第一位为1以外，其他的都为0。

所以最终的答案就是所有大于0的数加起来减一。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 1e6;
ll num[N],cnt[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> num[i];
			cnt[i] = num[i] - num[i - 1];//构造差分数组
		}
		ll ans = cnt[1]-1;
		for (int i = 2; i <= n; i++) {
			if (cnt[i] > 0)	ans += cnt[i];
		}
		cout << ans << endl;
	}
}