#|2018年ACM-ICPC亚洲青岛区域竞赛 - J:Books ACM题解|贪心

http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5837
Time Limit: 1 SecondMemory Limit: 65536 KB

文章图片

文章图片

文章图片

文章图片

文章图片
Problem solving report:
【#|2018年ACM-ICPC亚洲青岛区域竞赛 - J:Books】Description: 在n个书买m本书，买的规则如下:从左到右一次扫n本书,如果当前钱包里面的钱大于书的价钱,就买下来(必须买),问最多能带多少钱,钱数必须是非负整数,如果没有方案,就输出Impossible,如果可以带无限的钱,就输出Richman.
Problem solving: 贪心

先数数共有多少个0(0是必须要买的),假设ans个,如果ans>m,则没有方案,输出impossible;
然后再在剩下n-ans本书中买前m-ans本,得钱数sum;
对于剩下的求最小值,则最多可以带的钱为sum+min-1.
还有一种情况就是n与m相等的时候,则可以带无限的钱,输出Richman.

#include int a[100010]; int main() { long long sum; int t, x, k, n, m, ans, minn; scanf("%d", &t); while (t--) { minn = 1e9; sum = ans = k = 0; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &a[k]); if (!a[k]) ans++; else k++; } if (ans > m) printf("Impossible\n"); else if (n == m) printf("Richman\n"); else { m -= ans; for (int i = 0; i < m; i++) sum += a[i]; for (int i = m; i < k; i++) if (a[i] < minn) minn = a[i]; printf("%lld\n", sum + minn - 1); } } return 0; }