Codeforces355-div2B Vanya and Food Processor

Problem - B - Codeforces

Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed h and the processor smashes k centimeters of potato each second. If there are less than k centimeters remaining, than during this second processor smashes all the remaining potato.

高さ，秒間にを潰せるフードプロセッサーがある．高さ のじゃがいもが 個ある時に何秒で全て潰すことが出来るか？(indexの小さい順に崩していく)．
潰す順番を変更出来ないので，単純に入れて潰す． の時には次のを入れて潰す．そうでないの時は潰してから入れる．

Code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <stack>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  ll n;
  cin >> n;

  ll k, h;
  cin >> h >> k;

  vector<ll> v(n);
  rep(i, n) cin >> v[i];

  ll ans = 0, sum = 0;
  rep(i, n) {
      if(sum + v[i] <= h) sum += v[i];
      else {
          sum = v[i];
          ans++;
      }

      ans += sum / k;
      sum %= k;
  }

  if(sum != 0) ans++;

  cout << ans << endl;

  return 0;
}

本番は順番を変更出来るものだと勘違いしていて，pretestが延々と通らずに泣いていた．順番が変更出来る場合は，大きいものから入れれるなら入れて，入りきらなくなったら潰す．を繰り返していたのですが，この貪欲はあっているのかわからない．

Jun 2nd, 2016
codeforces