ZOJ - 4067

DreamGrid went to the bookshop yesterday. There are $n$ books in the bookshop in total. Because DreamGrid is very rich, he bought the books according to the strategy below:
Check the $n$ books from the 1st one to the $n$-th one in order.
For each book being checked now, if DreamGrid has enough money (not less than the book price), he’ll buy the book and his money will be reduced by the price of the book.
In case that his money is less than the price of the book being checked now, he will skip that book.
BaoBao is curious about how rich DreamGrid is. You are asked to tell him the maximum possible amount of money DreamGrid took before buying the books, which is a non-negative integer. All he knows are the prices of the $n$ books and the number of books DreamGrid bought in total, indicated by $m$.
Input
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $0 \le m \le n$), indicating the number of books in the bookshop and the number of books DreamGrid bought in total.
The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), where $a_i$ indicates the price of the $i$-th book checked by DreamGrid.
It’s guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.
Output
For each test case output one line.
If it’s impossible to buy $m$ books for any initial number of money, output “Impossible” (without quotes).
If DreamGrid may take an infinite amount of money, output “Richman” (without quotes).
In other cases, output a non-negative integer, indicating the maximum number of money he may take.
Sample Input
4
4 2
1 2 4 8
4 0
100 99 98 97
2 2
10000 10000
5 3
0 0 0 0 1
Sample Output
6
96
Richman
Impossible

思路：
分三种情况：

  1. 0圆书的数量大于m，这种情况是不可能的。因为0圆书肯定买得起，即Impossible。
  2. n=m，即DreamGrid 买了所有书，这样他手上剩下的钱是任意的，即Richman。题目给出$m\leq n$了。
  3. 其他情况
    对于其他情况，就需要具体计算了。根据题意，0圆书肯定必买，所以先(m-=0圆书数量)，然后再按顺序买完(m-(0圆书数量)本书)，然后他剩下的钱就是剩下的书中最便宜的价格-1，让他刚好买不起。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int Price[100005];
int n, m;
int T;


int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n,&m);
		int Zeros = 0;//0圆书数量
		for (int i = 0; i < n; ++i) {
			scanf("%d", &Price[i]);
			if (Price[i] == 0) {
				++Zeros;
			}
		}
		if (Zeros > m) {
			puts("Impossible");
			continue;
		}
		else if (n == m) {
			puts("Richman");
			continue;
		}
		else {
			if (m == 0) {//这不也许不必要，可以融入else里
				int Ans = 2000000000;
				for (int i = 0; i < n; ++i) {
					Ans = min(Ans, Price[i]);
				}
				printf("%d\n", Ans - 1);
				continue;
			}
			else {
				m -= Zeros;
				long long Ans = 0;
				int Cnt = 0;
				int i = 0;
				for (; i < n; ++i) {
					if (Price[i] == 0) {
						continue;
					}
					++Cnt;
					if (Cnt <= m) {
						Ans += Price[i];
					}
					else {
						break;
					}
				}
				//手上的余钱
				int Tail = 2000000000;
				for (; i < n; ++i) {
					if (Price[i] == 0) {
						continue;
					}
					Tail = min(Tail, Price[i]);
				}

				printf("%lld\n", Ans + Tail - 1);
				continue;

			}
		}
	}
	return 0;
}