第一次组队赛心情过于激动
I(2257): Intergalactic Bidding
原出处：GYM101933I
Description
Today the Intergalactic Council of Pebble Coins (ICPC) conducted an intergalactic auction of the Neutronium Chaos Pebble Coin (NCPC). This coin, which was forged in the Ancient Coin Machine (ACM), is rumored to be the key to ruling the universe.
Due to the extremely competitive nature of the auction, as well as the odd mechanics of the intergalactic currency used (far too advanced for mere mortals to understand), the auction was conducted with the following rules:
-
only one participant was allowed to make a bid at a time,
-
each participant was only allowed to make one bid, and
-
a participant making a bid had to bid at least twice the amount of the highest bid at the time.
The first participant making a bid was allowed to make a bid of any positive amount.
After the auction there were a lot of sore losers -- understandably, having just lost their chance at world domination. To make the losers feel a little better and prevent possible rioting, the ICPC has decided to hold a lottery for the participants. The winners of the lottery are determined as follows. The ICPC picks a random number s. A group of participants is called winning if the sum of their bets from the auction is equal to s. A participant wins the lottery and receives a prize -- a shiny Pebble Coin -- if they belong to any winning group of participants.
Given the names of the participants, the bets that they made, and the random number s chosen by the ICPC, help them determine which participants won the lottery.
Input
The first line of input contains two integers n and s, where 1 ≤ n ≤ 1 000 is the number of participants, and 1 ≤ s < 101 000 is the random number chosen by the ICPC.
Then follow n lines describing the participants. Each line contains a string t and an integer b, where t is the name of a participant, and 1 ≤ b < 101 000 is the amount of his bet. The name of each participant is unique and consists of between 1 and 20 letters from the English alphabet.
Output
Output an integer k denoting the number of participants that won the lottery. Then output k lines containing the names of the participants that won the lottery, one per line, in any order.
Sample Input
5 63 Vader 3 Voldemort 7 BorgQueen 20 Terminator 40 Megatron 101 --------------------------- 4 1112 Blorg 10 Glorg 1000 Klorg 1 Zlorg 100
Sample Output
3 BorgQueen Terminator Vader --------------------- 0
思路：首先看数据范围得写大整数，（比赛的时候一直不相信要写），然后根据每次出价竞拍大于等于前一次的两倍可知，从大到小选，若这个数小于还需要的数，那就必须选这个，不然哪怕后续所有数都选上都会小于这个数。
因此，该题解法为贪心+大整数
ACODE:
//7777777
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<queue>
#include<utility>
#include<vector>
#include<map>
#define lson l , m , rt << 1
#define rson m+1 , r , rt << 1 | 1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const double pi = 3.1415926535;
const double eps = 1e-6;
const int MXN = 1e3 + 7;
const int MXM = 1e8 + 10;
const int MX = 1e3 + 7;
const int maxbit = 18;
const double val = pi/180.0;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
struct Big{
char x[1005]; int len; string s;
bool operator == (const Big &A) const{
if(A.len != len) return 0;
for(int i = 0;i < len;++i) if(A.x[i] != x[i]) return 0;
return 1;
}
bool operator < (const Big &A) const{
if(A.len != len) return len < A.len;
for(int i = len - 1;i >= 0;--i) if(A.x[i] !=x[i]) return x[i] < A.x[i];
return 0;
}
Big operator + (const Big &A) const{
Big ans = *this;
for(int i = 0;i < A.len;++i){
ans.x[i] = ans.x[i] + A.x[i];
}
int mx = max(A.len,len);
int f = 0;
for(int i = 0;i < mx+1;++i){
if(ans.x[i] >= 10){
ans.x[i]-=10;
++ans.x[i+1];
}
if(ans.x[i]){
ans.len = i + 1;
f = 1;
}
}
if(!f) ans.len = 1;
return ans;
}
Big operator - (const Big &A) const{
Big ans = *this;
int f = 0;
for(int i = 0;i < A.len;++i){
ans.x[i] = ans.x[i] - A.x[i];
}
int mx = max(A.len,len);
for(int i = 0;i < mx+1;++i){
if(ans.x[i] < 0){
ans.x[i]+=10;
--ans.x[i+1];
}
if(ans.x[i]){
ans.len = i+1;
f = 1;
}
}
if(!f) ans.len = 1;
return ans;
}
void read(){
cin >> s;
len = s.size();
for(int i = 0;i < len;++i) x[len-i-1] = s[i] - '0';
s.clear();
}
void write(){
for(int i = len - 1;i >= 0;--i) printf("%d",x[i]);
putchar('
');
}
}s,zero;
//Big integer zero means empty
int n;
struct node{
string name;
Big A;
bool operator < (const node & a) const{
return A < a.A;
}
}a[MX];
//index of the answer
vector<int> ans;
int main()
{
zero.x[0] = 0;
zero.len = 1;
scanf("%d",&n);
s.read();
for(int i = 1;i <= n;++i){
cin >> a[i].name;
a[i].A.read();
}
sort(a+1,a+1+n);
for(int i = n;i >= 1;--i){
//no operator '<='
if(a[i].A < s|| s == a[i].A){
ans.push_back(i);
s = s - a[i].A;
}
}
if(s == zero){
printf("%d
",(int)ans.size());
for(int i = 0;i < ans.size();++i){
cout << a[ans[i]].name << '
';
}
}
else printf("0
");
return 0;
}
fighting！