此文章可以使用目录功能哟↑(点击上方[+])
FZU Problem 2212 Super Mobile Charger
Accept: 0 Submit: 0
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
While HIT ACM Group finished their contest in Shanghai and is heading back Harbin, their train was delayed due to the heavy snow. Their mobile phones are all running out of battery very quick. Luckily, zb has a super mobile charger that can charge all phones.
There are N people on the train, and the i-th phone has p[i] percentage of power, the super mobile charger can charge at most M percentage of power.
Now zb wants to know, at most how many phones can be charged to full power. (100 percent means full power.)
Input
The first line contains an integer T, meaning the number of the cases (1 <= T <= 50.).
For each test case, the first line contains two integers N, M(1 <= N <= 100,0 <= M <= 10000) , the second line contains N integers p[i](0 <= p[i] <= 100) meaning the percentage of power of the i-th phone.
Output
For each test case, output the answer of the question.
Sample Input
3 10
100 99 90
3 1000
0 0 0
Sample Output
3
Hint
Problem Idea
解题思路:
【题意】
有一块含电量M%的超级电池,要给n部剩余电量p[i]%的手机充电
问最多能够充满几部手机(即,使得这些手机电量为100%)
【类型】
贪心+排序
【分析】
因为要尽可能多地充满手机,所以我们必定会挑电量高的手机优先充电(贪心体现在这里)
所以,我们只需将手机按照剩余电量的多少排个序,然后遍历一遍,从电量高的手机处理起,直到超级电池的电量耗完即可
【时间复杂度&&优化】
O(nlogn)
题目链接→FZU Problem 2212 Super Mobile Charger
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-12
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 105;
const int M = 100;
const int mod = 200907;
const int inf = 1000000007;
int s[N];
int main()
{int t,n,m,i,ans;scanf("%d",&t);while(t--){ans=0;scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%d",&s[i]);sort(s,s+n);for(i=n-1;i>=0&&m>0;i--)if(m-100+s[i]>=0)ans++,m-=(100-s[i]);printf("%d\n",ans);}return 0;
}