CodeForces - Help The Support Lady(贪心)
题目链接:http://codeforces.com/gym/102219/problem/K
Time limit per test 1.0 s Memory limit per test 256 MB
Description
Nina works as an IT support in a software company and always busy. The biggest issue she is facing is that sometimes she misses some deadlines. In their team the time needed to finish each customer request is estimated based on experience, 1≤x≤105. The moment a request is submitted, she has double of the estimated time to respond to the request, 2x. Meaning if the request A was submitted at 12pm and takes 2 hours to finish, she can wait 2 hours and then work on it for 2 hours and still finish the job on time, by 4 pm and the customer would be satisfied.
Sometimes there is not enough capacity and she has to pick up a lot of requests, and it is expected to miss some deadlines. But she needs your help, to see if arrange correctly what are the maximum requests she can finish before their deadlines.
Let's assume that she has the list of the requests and their deadline immediately as she starts working every day and she doesn't take any break until she is done with all of them.
Input
The first line contains integer m (1≤m≤20). Number of cases.
The second line contains integer n (1≤n≤105). Number of the requests.
The last line contains n integers ti (1≤ti≤109), separated by spaces. Estimated time each request should be responded so the customer would be happy.
Output
Print the case number and a single number - the maximum number of satisfied customer for each case.
Example
input
1
5
15 2 1 5 3
output
Case #1: 4
Note
If she responds to the request with this order 1, 2, 3, 5, 15, the only customer with the request that requires 5 hours wouldn't be happy.
Problem solving report:
Description: 给你每个请求的响应时间，求最大满意客户数。
Problem solving: 我们可以先完成那些响应时间比较短的，因为它们的截止时间短，同理，那些响应时间比较长的，截止时间长，所以我们把响应时间从小到大排一个序，然后就直接判断就行了。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 105;
int spt[MAXN];
int main() {
int t, n, cnt, kase = 0;
scanf("%d", &t);
while (t--) {
cnt = 0;
long long ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", spt + i);
sort(spt, spt + n);
for (int i = 0; i < n; i++) {
if (ans <= spt[i]) {//ans + spt[i] <= spt[i] * 2
cnt++;
ans += spt[i];
}
}
printf("Case #%d: %d\n", ++kase, cnt);
}
return 0;
}
