题意:
按顺序买书,遇到买不起的书就跳过,遇到买的起的书必须买。
他买了M本书,询问他最少有多少钱。
题解:
先计算价格为0的书的数量,这些书必须买,如果M小于这个数值,直接输出Impossible
然后遍历一遍挑选价格非0的书直到总数为M
然后遍历剩下的书,取价格最小值。
挑选的书籍的总价格加上最小值减一就是答案
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; typedef long long ll; int a[maxn]; int N,M; int T; int main () { scanf("%d",&T); while (T--) { scanf("%d%d",&N,&M); int numZr=0; for (int i=1;i<=N;i++) { scanf("%d",&a[i]); numZr+=a[i]==0; } if (M==N) { printf("Richman\n"); continue; } if (M<numZr) { printf("Impossible\n"); continue; } if (M>N) { printf("Impossible\n"); continue; } ll ans=0; int num=numZr; int Min=1e9; for (int i=1;i<=N;i++) { if (a[i]==0) continue; num++; if (num<=M) ans+=a[i]; if (num>M) { Min=min(Min,a[i]); } } ans+=Min-1; printf("%lld\n",ans); } return 0; }