NC21794. 鸡尾酒买罐子
描述
鸡尾酒喜欢罐子，有一天他到了一个罐子专卖店，他决定买好多好多罐子回家。但是专卖店快关门了，鸡尾酒必须尽快选购，他决定按顺序把罐子浏览一遍，如果他的钱花完了（钱数=0）或者已经走过了最后一个罐子，就会立即离开商店。
由于鸡尾酒不会掩饰自己对罐子的喜爱，所以只要他现有的钱大于等于当前看到的罐子的价格，他就会购买。
鸡尾酒有n元钱，并且想买m个罐子，你能帮他算算他应该至少带多少钱才能买到m个罐子吗？
输入描述
第一行包含三个整数n，m，k。n代表鸡尾酒最多能带的钱(0<=n<109)，m代表鸡尾酒想买的罐子数量，k代表商店里罐子的数量，保证商店至少有m个罐子(1<=m<=k<=300)。接下来一行包含k个整数，第i个数表示第i个罐子的价格pi。(0<=pi<=1000)
输出描述
输出鸡尾酒购买m个罐子至少需要带的钱数。
如果鸡尾酒无论如何都买不了m个罐子，输出 "poor chicken tail wine!"
示例1
输入:
5 2 3 1 2 3
输出:
3
示例2
输入:
1 2 2 100 100
输出:
poor chicken tail wine!
C++14(g++5.4) 解法, 执行用时: 63ms, 内存消耗: 364K, 提交时间: 2020-07-03 13:51:20
#include <stdio.h>
int n, m, c, i, j, k, s, a[305];
int ok(int x){
int i, j, k=0;
for(i=1; x>0 && i<=n; i++){
if(x >= a[i]) x -= a[i], k++;
}
return k >= c;
}
int main(){
scanf("%d%d%d", &m, &c, &n);
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
s += a[i];
}
if(m > s+1) m = s + 1;
for(i=1; i<=m; i++){
if(ok(i)) break;
}
if(i <= m) printf("%d\n", i);
else printf("poor chicken tail wine!\n");
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 111ms, 内存消耗: 492K, 提交时间: 2018-12-23 17:23:04
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[310],x,p;
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=k;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
x=i;
p=0;
for(int j=1;j<=k;j++){
if(x>=a[j]) x-=a[j],p++;
if(x==0) break;
}
if(p>=m){
cout<<i<<endl;
return 0;
}
}
cout<<"poor chicken tail wine!"<<endl;
return 0;
}