<< ABC049-C 白昼夢 | top | ABC046-C AtCoDeerくんと選挙速報 >>

スポンサーサイト

一定期間更新がないため広告を表示しています

スポンサードリンク | - | | - | - |

ABC048-C Boxes and Candies

問題文

N 個の箱が横一列に並んでいます。 最初、左から i 番目の箱には ai 個のキャンディが入っています。

すぬけ君は次の操作を好きな回数だけ行うことができます。

  • キャンディが 1 個以上入っている箱をひとつ選び、その箱のキャンディを 1 個食べる。

すぬけ君の目標は次の通りです。

  • どの隣り合う 2 つの箱を見ても、それらの箱に入っているキャンディの個数の総和が x 以下である。

目標を達成するために必要な操作回数の最小値を求めてください。

 

まず、どの箱もx以下になる必要があるので、とりあえずそれをしてしまう。

その後が問題。

真ん中から考えると難しいので端から小問題を順次解く感じでできないかなと考えてみる。

左端二つに注目する。もしこれらの和がxよりも大きいならキャンディを食べる必要があるが、左を食べるよりも右を食べるほうがいい。右を食べておけばその右の箱との和が有利になるから。なので右の箱を食べて条件を満たすようにする。これを繰り返せばok。貪欲法というやつか。

#include <iostream>
#include <vector>

int main()
{
	int N; std::cin >> N;
	int x; std::cin >> x;
	std::vector<int> a(N);
	for(auto &z : a) std::cin >> z;

	long long ans = 0;
	for(auto &z : a)
	{
		if(z > x)
		{
			ans += z-x;
			z -= z-x;
		}
	}
	for(int n=0; n<N-1; n++)//n:端の番号
	{
		int sum = a[n] + a[n+1];
		if(sum > x)
		{
			ans += sum-x;
			a[n+1] -= sum-x;
		}
	}
	std::cout << ans << std::endl;

	return 0;
}

 

ジャジャガッチ | C/C++ | 12:42 | comments(0) | trackbacks(0) |

スポンサーサイト

スポンサードリンク | - | 12:42 | - | - |
Comment









Trackback
URL:

07
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH