読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

CODE FESTIVAL 2016 予選B : D - Greedy customers

CODE FESTIVAL

問題リンク :
D: Greedy customers - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 : 日本語なので略

解法 :
(備忘録)
貪欲法。

1ずつ引いていけば良い?1を引けなくなったら2を、それもダメなら3を、...という流れで、
=> Sample Input 2 の答えが13になる
これでダメなケースとは?
...
Sample Input X

4
1
2
6
10

Sample Output X

4

Why?

1 2 6 10  P
1 2 3 10 (3)
1 2 3 6  (4)
1 2 3 2  (4)
Ans : 3.

1 2 6 10  P
1 2 1 10 (5)
1 2 1 7  (3)
1 2 1 4  (3)
1 2 1 1  (3)
Ans : 4.

引ける最小の値が大きくなってしまうような場合は一気に1まで値を引いてしまえばよいネ



コード :

#include<bits/stdc++.h>
 
using namespace std;

#define MAX 100010

int N;
long long A[MAX];
 
int main(){
  long long answer = 0, lower = 1LL;
  cin >> N;
  for(int i=0;i<N;++i) cin >> A[i];

  for(int i=0;i<N;++i) {
    if( lower == 1LL ) {
      answer += (A[i]-1LL);
      lower = 2LL;
      continue;
    }
    
    if( lower == A[i] ) {
      ++lower;
      continue;
    }
 
    if( lower > A[i] ) continue;    
 
    long long coef = A[i] / lower;
    if( ( A[i] - coef * lower ) == 0LL ) {
      --coef;
    }
    answer += coef;
  }
  cout << answer << endl; 
  return 0;
}