Android教程網
  1. 首頁
  2. Android 技術
  3. Android 手機
  4. Android 系統教程
  5. Android 游戲
 Android教程網 >> Android技術 >> 關於Android編程 >> Codeforces 388A Fox and Box Accumulation(貪心)

Codeforces 388A Fox and Box Accumulation(貪心)

編輯:關於Android編程

題目鏈接:Codeforces 388A Fox and Box Accumulation


題目大意:給出n個箱子,每個箱子告訴你說最多可以在這個箱子上面放幾個箱子,問說最少需要壘多少落。


解題思路:x最大才105,用一個cnt數組記錄下每種箱子的個數,然後從最小的開始一直往上加,直到不能加為止。


#include 
#include 
#include 

using namespace std;
const int N = 105;

int n, cnt[N], tmp;

void init () {
	int a;
	tmp = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		tmp = max(a, tmp);
		cnt[a]++;
	}
}

void set(int x, int c) {
	if (x > tmp) return;

	if (c > x || cnt[x] == 0) {
		set(x+1, c);
	} else {
		cnt[x]--;
		set(x, c+1);
	}
}

int solve () {
	int ans = 0;
	for (int i = 0; i <= tmp; i++) {
		while (cnt[i]) {
			set(i, 0); 
			ans++;
		}
	}
	return ans;
}

int main () {
	memset(cnt, 0, sizeof(cnt));
	init();
	printf("%d\n", solve());
	return 0;
}


  1. 上一頁:
  2. 下一頁:
熱門文章
閱讀排行版
Copyright © Android教程網 All Rights Reserved