题目:
小A有一个神奇口袋,里面可以装各个平方数,口袋的负载量就是口袋里所有数字之和。当负载量超过L的时候不能再装平方数,现在给定n个数,从左往右筛选其中的平方数,并依次将平方数放入口袋,编成程序,输出口袋里能装下几个平方数。平方数就是一个愁数乘以自己的结果(例如:1、4、9、16、…)。例如输入L为100,n为5,接下来的5个数分别是49、19、36、25、73,则口袋里只装了49和36两个平方数,所以输出2。
分析:
输入L是100,n是5,接下来的数是49、19、36、25、73。那么符合条件的平方数是49(7²)、36(6²)、25(5²),但装的时候顺序装。先装49,总和是49。接着检查19不是平方数跳过。然后36,总和49+36=85,没超过100,所以装进去。接着25的话,加上85是110,超过100了,所以不能装。所以最终装了两个平方数49和36,输出2。
#include <iostream>
#include <cmath> // 包含sqrt函数所需的头文件
using namespace std;int main() {int L, n;cin >> L >> n; // 输入负载量L和数字个数nint sum = 0, count = 0; // 初始化口袋的总和和计数器for (int i = 0; i < n; i++) {int x;cin >> x; // 读取当前数字// 判断x是否为非负且是平方数if (x >= 0 && (int)sqrt(x) * (int)sqrt(x) == x) { // 检查装入后是否超过负载量if (sum + x <= L) { sum += x; // 将x加入总和cout << x << " "; // 输出能被放进口袋的数字 count++; // 计数器加1} else {break; // 超过负载量,终止循环}}}cout << endl;cout << count << endl; // 输出能装下的平方数个数return 0;
}