解题思路
这是一个时间累加问题:
- 游乐园有
个项目,每个项目需要
分钟
- 总共有
分钟的时间限制
- 需要计算在时间限制内能玩的项目总时间
解题步骤:
- 将所有项目按时间排序
- 从小到大累加项目时间
- 当累加和大于或等于
时停止
- 返回累加的总时间
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 101;
int main() {
int n;
long t;
cin >> n >> t;
// 读入项目时间
long a[MAXN];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 排序
sort(a, a + n);
// 计算可以玩的总时间
long sum = 0;
for (int i = 0; i < n; i++) {
if (t > sum) {
sum += a[i];
}
if (t == sum || sum > t) {
break;
}
if (t < sum) {
sum += a[n-1];
}
}
cout << sum << endl;
return 0;
}
import java.util.*;
public class Main {
static final int MAXN = 101;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long t = sc.nextLong();
// 读入项目时间
long[] a = new long[MAXN];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
// 排序
Arrays.sort(a, 0, n);
// 计算可以玩的总时间
long sum = 0;
for (int i = 0; i < n; i++) {
if (t > sum) {
sum += a[i];
}
if (t == sum || sum > t) {
break;
}
if (t < sum) {
sum += a[n-1];
}
}
System.out.println(sum);
sc.close();
}
}
# 读入数据
n, t = map(int, input().split())
a = list(map(int, input().split()))
# 排序
a.sort()
# 计算可以玩的总时间
sum_time = 0
for i in range(n):
if t > sum_time:
sum_time += a[i]
if t == sum_time or sum_time > t:
break
if t < sum_time:
sum_time += a[n-1]
print(sum_time)
算法及复杂度
- 算法:贪心
- 时间复杂度:
,主要是排序的时间
- 空间复杂度:
,用于存储项目时间数组