题意：n个人竞价拍卖宝石，宝石价值s块钱，求哪些人出的钱加起来刚好是s
题解：
根据题意，当前人出的钱一定是全场人出的钱的两倍还多。那我们就可以对每个人出的钱排序,
从大的开始取，假设当前为x，如果s>=x，一定要取x，因为如果不取x我们就得取比x小的那些数，但是就算把比x小
的数全加起来不比x大，所以x必须被取走！
举例：2 5 13 28 50，s=57，发现50小于等于57，取之，s=7,然后28>s，不取，然后13也不能取，最后把5和2取完
因为钱数很大，这里用JAVA里的BigInteger类处理。
一开始想着用结构体存人名字和钱，然后重载运算符再排序，结果发现JAVA不支持重载运算符。。。
然后发现每个人的钱数肯定不同，便祭出了map；
后来又发现还他妈不支持biginteger排序。。。
好吧，大不了我手写个排序咯
1 //package 实验; 2 import java.math.BigInteger; 3 import java.util.Scanner; 4 import java.util.*; 5 import java.io.*; 6 7 public class Main { 8 public static void main(String [] args){ 9 BigInteger t = BigInteger.valueOf(1); 10 Map<BigInteger, String> mp = new HashMap<BigInteger, String>(); 11 BigInteger a[]=new BigInteger[1005]; 12 Scanner cin = new Scanner(System.in); 13 int n=cin.nextInt(); 14 BigInteger k=cin.nextBigInteger(); 15 String s=""; 16 for(int i=1;i<=n;i++) { 17 s=cin.next(); 18 a[i]=cin.nextBigInteger(); 19 mp.put(a[i], s); 20 } 21 for(int i=n;i>=1;i--) { 22 for(int j=1;j<i;j++) { 23 if(a[j].compareTo(a[j+1])==1) { 24 t=a[j]; 25 a[j]=a[j+1]; 26 a[j+1]=t; 27 } 28 } 29 } 30 String s1[]=new String[1005]; 31 int cnt=0; 32 for(int i=n;i>=1;i--) { 33 if(k.compareTo(a[i])>=0) { 34 k=k.subtract(a[i]); 35 s1[++cnt]=mp.get(a[i]); 36 37 } 38 } 39 if(k.equals(BigInteger.ZERO)) { 40 System.out.println(cnt); 41 for(int i=1;i<=cnt;i++) { 42 System.out.println(s1[i]); 43 } 44 } 45 else System.out.println(0); 46 } 47 }
CSUOJ2257: Intergalactic Bidding
原文：https://www.cnblogs.com/ccsu-kid/p/10526132.html