HDACM 1009
贪心算法
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc= new Scanner(System.in);while (sc.hasNext()) {int m = sc.nextInt();int n = sc.nextInt();if (n==-1&&m==-1) {break;}int j[] = new int[n];int f[] = new int[n];double v[] = new double[n];for (int i = 0; i < n; i++) {j[i] = sc.nextInt();f[i] = sc.nextInt();if (f[i]==0) {v[i] = Double.MAX_VALUE;}else{v[i] = 1.0*j[i]/f[i];}}for (int i = 0; i < v.length; i++) {for (int k = i+1; k < v.length; k++) {if (v[i]<v[k]) {int t = j[i];j[i] = j[k];j[k] = t;t = f[i];f[i] = f[k];f[k] = t;double tt = v[i];v[i] = v[k];v[k] = tt;}}}double ans = 0;int i = 0;while(m>0&&i<n){if (f[i]>m) {ans += v[i]*m;break;}ans += j[i];m -= f[i];i++;}System.out.printf("%.3f",ans);System.out.println();}sc.close();}
}