2018 青岛ICPC区域赛 J Books

J Books

题意： 在n个书买m本书，买的规则如下：
从左到右一次扫n本书，如果当前钱包里面的钱大于书的价钱，就买下来（必须买）
问最多能带多少钱，钱数必须是非负整数，如果没有方案，就输出impossible ,如果可以带无限的钱，就输出Richman
贪心：

1. 先数数共有多少个0，假设cnt个，如果cnt > m，impossible
2. 然后再在剩下n-cnt本数中买前m-cnt 个
3. 对于剩下的求最小值

LL a[maxn];
int main(void)
{
   int T;
   cin>>T;
   while(T--){
        int n,m;
        scanf("%d %d",&n,&m);
        int zeros = 0;
        int nn = 1;
        for(int i = 1;i <= n; ++i){
            scanf("%lld",&a[nn]);
            if(a[nn] == 0) zeros++;
            else nn++; 
        }
        if(zeros > m){
            puts("Impossible");
            continue;
        }
        else if(n ==m ){
            puts("Richman");
            continue;
        }
        else {
            m -= zeros;
            LL ans = 0;
            for(int i = 1;i <= m; ++i){
                ans += a[i];
            }
            LL _min = 1e9;
            for(int i = m+1;i < nn; ++i){
                _min = min(a[i],_min);
            }
            printf("%lld\n",ans+_min-1);
        }
   }

   return 0;
}