ZOJ4067 Books(思维)

题意:

按顺序买书,遇到买不起的书就跳过,遇到买的起的书必须买。

他买了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;
}

 

上一篇:迭代器模式


下一篇:SSM整合(一个简单的图书管理系统的实现:增删改查基本功能的实现)