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 必须打出的最少顺子次数。

样例

输入

1
2
3
4
5
6
5
2
4
1
2
3

输出

1
6

解释

Bessie 可以打出以下顺子：

  • 从 1 到 5 的顺子
  • 从 1 到 2 的顺子
  • 从 4 到 5 的顺子
  • 两次从 2 到 2 的顺子
  • 从 5 到 5 的顺子

总共需要 6 次顺子来打出所有的牌。

解题

思路

算法：贪心 差分

这题首先一眼贪心，其次看到题目从i到j全部减一马上就想到差分，这很差分的性质。因为差分只要一个地方减一，后面相应位置对应的原数值都会改变，和本题思路很贴切。

所以写出差分（拿上面的测试点当例子）
2 2 -3 1 1

从第一个数字开始模拟发现减一后，第一堆牌和后面全部堆都会出一张牌，再减一后第一、二堆会再出一张，而第三堆就因为没牌而不会再出了，后面也就无法连续起来。现在除了两次牌，第一堆已经清零了，那就继续往后推。第二堆现在剩2张牌，显然同前面一样要出2次，而第三堆及以后都不会出牌。然后就发现了规律，差分为正的话，这个差分的值都需要加在出牌次数里面，而负的差分就不需要了，因为如果差分是负的，等计算到这堆牌的时候肯定已经没牌了，因为牌比前面少跟着前面早出完了（0也同理）。

总结一下，就是所有正的差分的和就是全部最少的出牌次数。古德~！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}