解题思路

这是一个时间累加问题:

  1. 游乐园有 个项目,每个项目需要 分钟
  2. 总共有 分钟的时间限制
  3. 需要计算在时间限制内能玩的项目总时间

解题步骤:

  1. 将所有项目按时间排序
  2. 从小到大累加项目时间
  3. 当累加和大于或等于 时停止
  4. 返回累加的总时间

代码

#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)

算法及复杂度

  • 算法:贪心
  • 时间复杂度:,主要是排序的时间
  • 空间复杂度:,用于存储项目时间数组