P3078[USACO13MAR] Poker Hands S
P3078[USACO13MAR] Poker Hands S
https://www.luogu.com.cn/problem/P3078
前言
学习差分后写的第一道题，直接给我干懵逼，题解都看不懂……吃了个晚饭后开窍写出来了，遂成此篇。
题目
翻译版本
Bessie 和她的朋友们正在玩一种独特的扑克游戏，使用一副有 (N) 种不同牌面的牌，牌面编号为 1 到 (N)（普通扑克有 (N = 13) 种牌面）。在这个游戏中，玩家只能打出一种牌型：选择一张牌面为 (i) 的牌和一张牌面为 (j) 的牌，打出从 (i) 到 (j) 的所有牌。这种牌型称为“顺子”。
Bessie 当前手上有 (a_i) 张牌面为 (i) 的牌（(0 \le a_i \le 100000)）。帮助她计算出她打出所有牌所需的最少顺子次数。
输入格式
- 第 1 行：整数 (N)。
- 第 2 到 (1+N) 行：第 (i+1) 行包含一个整数 (a_i)。
输出格式
- 第 1 行：Bessie 必须打出的最少顺子次数。
样例
输入
5
2
4
1
2
3
输出
6
解释
Bessie 可以打出以下顺子：
- 从 1 到 5 的顺子
- 从 1 到 2 的顺子
- 从 4 到 5 的顺子
- 两次从 2 到 2 的顺子
- 从 5 到 5 的顺子
总共需要 6 次顺子来打出所有的牌。
解题
思路
算法：贪心 差分
这题首先一眼贪心，其次看到题目从i到j全部减一马上就想到差分，这很差分的性质。因为差分只要一个地方减一，后面相应位置对应的原数值都会改变，和本题思路很贴切。
所以写出差分（拿上面的测试点当例子）
2 2 -3 1 1
从第一个数字开始模拟发现减一后，第一堆牌和后面全部堆都会出一张牌，再减一后第一、二堆会再出一张，而第三堆就因为没牌而不会再出了，后面也就无法连续起来。现在除了两次牌，第一堆已经清零了，那就继续往后推。第二堆现在剩2张牌，显然同前面一样要出2次，而第三堆及以后都不会出牌。然后就发现了规律，差分为正的话，这个差分的值都需要加在出牌次数里面，而负的差分就不需要了，因为如果差分是负的，等计算到这堆牌的时候肯定已经没牌了，因为牌比前面少跟着前面早出完了（0也同理）。
总结一下，就是所有正的差分的和就是全部最少的出牌次数。古德~！
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 100010;
LL n, t, sum = 0, b[N];
int main() {
cin >> n;
for (LL i = 1; i <= n; i++) {
scanf("%lld", &t); // 数组a输入
b[i] += t, b[i + 1] -= t; // 计算差分b
if (b[i] > 0) sum += b[i]; // 差分大于0就加到结果里面
}
cout << sum;
return 0;
}