Codeforces #35 (div2) D "Animals"

問題：http://www.codeforces.com/contest/35/problem/D

プラクティス．

n日まで毎日なんかの動物がやってきて居座るようだけど断ることもできる．居座る動物は来た日からn日まで毎日メシを食う．n日まで養う事ができる動物の最大数を求める．

各動物がn日までに消費する量はn日までの残り日数×一日の消費量なので，各動物がn日までに消費する量を予め計算しておいて，それが少ない動物から受け入れてゆくといいらしい．

import java.io.File;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class D_Animals {
	public static void main(String[] args) throws Exception {
		File in = new File("input.txt"), out = new File("output.txt");
		Scanner s;
		PrintWriter pw;
		if (in.exists()) {
			s = new Scanner(in);
			pw = new PrintWriter(out);
		} else {
			s = new Scanner(System.in);
			pw = new PrintWriter(System.out);
		}
		int n = s.nextInt(), k = s.nextInt();
		int[] a = new int[n];
		for (; n > 0;) {
			a[n - 1] = s.nextInt() * n--;
		}
		Arrays.sort(a);
		int c = 0;
		for (int i = 0; i < a.length; ++i) {
			if (k - a[i] >= 0) {
				k -= a[i];
				++c;
			}
		}
		pw.println(c);
		pw.close();
	}
}