CODE FESTIVAL 2016 予選B : D - Greedy customers
問題リンク :
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; }