首页 > 其他 > 详细

CSUOJ2257: Intergalactic Bidding

时间:2019-03-13 20:50:23      阅读:189      评论:0      收藏:0      [点我收藏+]

题意: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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!