描述
查看信息
国王派你出来搜集一种漂亮的宝石，可是无奈这种宝石太过稀有，整个大陆上只有一个“黑心”市场有货，这处市场有 n 家商户，每家都售卖这种宝石，你非常开心，但是市场上有一个规则：
在任意一家商户都可以买到这种宝石，并且无限供应（但一次只能买 1 颗），初始售价 ai 由商户自己决定，不过每次商户卖掉 1 颗宝石后，都要把价格涨为原来的 2 倍。
现在你身上带了 x 元钱，最多能买走多少颗宝石？
输入格式
第一行两个整数 n 和 x ，表示商户的数目和身上的钱数。
第二行 n 个整数，表示每一家商户的宝石初始售价 ai 。
输出格式
一个整数，表示最多能买走多少颗宝石。
样例输入
3 10
1 2 3
样例输出
4
问题提示
【说明/提示】
第1家：1元，涨价为2元
第2家：2元，涨价为4元
第1家：2元，涨价为4元
第3家：3元，涨价为6元
【数据范围】
对于 30% 的数据：1≤n≤100 ，1≤ai≤10 ，1≤x≤106 ；
对于 60% 的数据：1≤n≤105 ，1≤ai≤104 ，1≤x≤109 ；
对于 100% 的数据：1≤n≤105 ，1≤ai≤109 ，1≤x≤1018 ；
想看一下代码
这个问题其实就是考你数组和排序，其使用枚举算法就能很快解决，就是会出一点小问题。以下是我的代码：
#include <iostream>
using namespace std;
int n,x,ai[106]; //全局变量：店铺数量，钱的数量，每个店铺的初始价格
void putin(){ //输入部分函数，无返回值
cin >> n >> x;
for (int i = 0;i < n;i ++){
cin >> ai[i];
}
}
int paixu(int s[106],int y){ //进行排序，返回值为最便宜店面的价格
int t;
for (int i = 0;i < y;i ++){
for (int j = 0;j < y - i;j ++){
if (s[j + 1] < s[j]){
t = s[j];
s[j] = s[j + 1];
s[j + 1] = t;
}
}
}
return s[1];
}
void zhuanhuan(int s[106],int y){
for (int i = 1;i < y;i ++){ //将s数组里面的内容装入全局数组ai中以便转换
ai[i] = s[i];
}
}
int buydiamond1(int an,int ax){ //购买函数1，返回值为能够购买的宝石数量diam
int list[an];
int diam = 0;
for (int i = 0;i < an;i ++){
list[i] = ai[i];
}
for (int i = 0;ax >= paixu(ai,an);i ++){
if (list[i] == paixu(ai,an)){
diam ++;
ax -= list[i];
list[i] *= 2;
zhuanhuan(list,an);
for (int i = 0;i < an;i ++){
ai[i] = list[i];
}
}
}
return diam;
}
int buydiamond2(int an,int ax){ //购买函数2，返回值为能够购买的宝石数量diam
int diam = 0;
for (int i = 0;ax >= paixu(ai,an);i ++){
if (ai[i] == paixu(ai,an)){
diam ++;
ax -= ai[i];
ai[i] *= 2;
}
}
return diam;
}
int main(){
int diam;
bool tof;
putin();
for (int i = 1;i < n;i ++){
if (ai[n - 1] == ai[n]) tof = false;
else tof = true;
}
if (tof){
diam = buydiamond1(n,x);
}
else{
diam = buydiamond2(n,x);
}
cout << diam;
return 0;
}
你看可以不？