題意：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取完，s=0

因為錢數很大，這里用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 }

?

轉載于:https://www.cnblogs.com/ccsu-kid/p/10526132.html

總結

以上是生活随笔為你收集整理的CSUOJ2257: Intergalactic Bidding的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。