洛谷 P3078 [USACO13MAR]扑克牌型Poker Hands
JDOJ 2359: USACO 2013 Mar Silver 1.Poker Hands
题目描述
Problem 1: Poker Hands [Albert Gu, 2011]
Bessie and her friends are playing a unique version of poker involving a
deck with N (1 <= N <= 100,000) different ranks, conveniently numbered 1..N
(a normal deck has N = 13). In this game, there is only one type of hand
the cows can play: one may choose a card labeled i and a card labeled j and
play one card of every value from i to j. This type of hand is called a
"straight".
Bessie's hand currently holds a_i cards of rank i (0 <= a_i <= 100000). Help
her find the minimum number of hands she must play to get rid of all her
cards.
输入
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains the value of a_i.
输出
* Line 1: The minimum number of straights Bessie must play to get rid
of all her cards.
样例输入
5 2 4 1 2 3
样例输出
6
提示
OUTPUT DETAILS:
Bessie can play a straight from 1 to 5, a straight from 1 to 2, a straight
from 4 to 5, two straights from 2 to 2, and a straight from 5 to 5, for a
total of 6 rounds necessary to get rid of all her cards.
题目大意：
一个牛有N堆牌，每堆牌数量不等。一只牛一次可以将第i张到第j张各打一张出去，问最少几次打完
题解：
贪心。
当然也可以用区间修改的线段树做一个优化...（我就是做线段树做到这题的，线段树代码巨长无比）然而贪心思想就可以很短的代码AC。
我们来思考一下，这道题就是给定序列，区间修改直到序列为空，最少修改次数是多少。我们很容易得出，因为修改区间是没有限制的，所以我们贪心地想，一次修改的区间越长越好。也就是说，我们找一段连续的（中间不含0的）序列，只需要都减去其中的最小值，然后答案累加上这个最小值，最后就肯定能保证这个答案的正确性。
所以有了这个分析，这道题就变成了一道模拟题。
请大家观赏AC代码：
(再次提醒long long)
#include <cstdio>
#define ll long long
using namespace std;
ll n,a,h,ans;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a);
if(a>h)
ans+=(a-h);
h=a;
}
printf("%lld",ans);
return 0;
}