时间: 500ms / 空间: 65536KiB / Java类名: Main
背景
小天很喜欢玩球球大作战这个游戏，大家也应该都玩过。游戏规则是：移动自己的球，移动到别人的球（一定要比自己的球小）的位置上，就可以吃掉别人的球，把别人的球的体积值加到自己的球上。还有分身、吐球等功能，但本题不考虑。
描述
作为一个OIer，小天给自己做了一个超牛的外挂：让自己的球瞬间移动到场内的任何位置！！！这意味着小天可以瞬间移动到任何一个比自己小的球上，把它吃掉。现在，小天只用外挂来瞬移，每次瞬移只能吃掉一个球。
现在房间内有n个大小不一的球，小天至少瞬移吃球多少次，才能比剩下的所有球都大呢？
样例1：
输入
3 5
10 7 4
输出
2
样例2：
输入3 5
12 2 4
输出
-1
11
输入格式
第一行两个正整数n,s，分别表示场内别人球的个数、小天的球的初始大小。
第二行n个正整数，表示这些球各自的大小。
输出格式
一行一个整数，表示变成第一至少需要吃人的次数。如果怎么也无法变成第一，则输出两行，第一行为-1，第二行为最大能达到的体积值。
备注
数据限制：
n<=30000
其他数字保证32位能存下
解法一：优先队列。10个点总用时45ms
每次把小于当前体积的数压进优先队列（大根堆），每次贪心取堆顶元素吃掉，记录何时成为最大球。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 const int mxn=30010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 int a[mxn]; 17 int n; 18 priority_queue <int,vector<int>,less<int> >q; 19 int pos,s=0; 20 int main(){ 21 n=read();s=read(); 22 int i,j; 23 for(i=1;i<=n;i++) a[i]=read(); 24 sort(a+1,a+n+1); 25 pos=1;bool flag=0; 26 int cnt=0; 27 while(++cnt){ 28 while(a[pos]<s && pos<=n){q.push(a[pos]);pos++;} 29 if(pos>n && !flag){ 30 flag=1;printf("%d ",cnt-1); 31 } 32 if(q.empty())break; 33 s+=q.top();q.pop(); 34 } 35 if(!flag)printf("-1 %d ",s); 36 return 0; 37 }
解法二：暴力二分查找。 10个点总用时638ms
将所有数排序，每次二分查找当前能吃掉的最大球，如果这个球之前已经被吃掉了，就从此处向前暴力找第一个没被吃掉的球来吃。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=30010; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 int a[mxn]; 16 int smm=0,mx=0; 17 int n,s; 18 bool vis[mxn]; 19 int main(){ 20 n=read(); 21 s=read(); 22 int i,j; 23 for(i=1;i<=n;i++){ 24 a[i]=read(); 25 smm+=a[i]; 26 } 27 sort(a+1,a+n+1); 28 mx=a[n]; 29 int cnt=0; 30 int ans=0; 31 bool flag=0; 32 int pos=0; 33 for(i=1;i<=n;i++){ 34 int l=1,r=n; 35 int mid; 36 while(l<=r){ 37 mid=(l+r)>>1; 38 if(s<=a[mid]){ 39 r=mid-1; 40 } 41 else{ 42 pos=mid; 43 l=mid+1; 44 } 45 } 46 l=pos; 47 while(vis[l])l--; 48 s+=a[l]; 49 cnt++; 50 if(l)vis[l]=1; 51 if(s>mx && !flag){ 52 flag=1; 53 ans=cnt; 54 } 55 } 56 if(ans==0)printf("-1 %d ",s); 57 else printf("%d ",ans); 58 return 0; 59 }
暴力多吼呀！