【华为OD机试】虚拟游戏理财（动态规划dp实现Java&Python&C++&JS）

这篇文章距离上次修改已过236天，其中的内容可能已经有所变动。

题目描述：

在一个虚拟的游戏中，有一个财库系统，用户可以存钱或者消费。系统会记录每一笔交易，包括交易时间和交易金额。现在给你一系列的交易记录，请你计算在给定时间范围内，用户的财富变化情况。

输入描述：

第一行包含两个整数n和m，表示交易记录的数量和询问的时间范围数量。

接下来n行，每行包含两个整数ti和vi，表示第i笔交易的时间和金额。

接下来m行，每行包含两个整数ai和bi，表示查询的时间范围，[ai, bi]。

输出描述：

对于每个查询时间范围，输出一个整数，表示在该时间范围内用户的财富总变化。

示例输入：

2 6

3 7

4 8

5 9

6 10

1 5

4 6

示例输出：

-15

解决方案：

这是一个典型的动态规划问题，可以通过维护一个前缀和数组来解决。

Java代码示例：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] transactions = new int[n][2];
        for (int i = 0; i < n; i++) {
            transactions[i][0] = scanner.nextInt(); // ti
            transactions[i][1] = scanner.nextInt(); // vi
        }
        scanner.close();

        // 对交易按时间进行排序
        Arrays.sort(transactions, (a, b) -> a[0] - b[0]);

        long[] prefixSum = new long[n];
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                prefixSum[i] = prefixSum[i - 1] + transactions[i][1];
            } else {
                prefixSum[i] = transactions[i][1];
            }
        }

        for (int i = 0; i < m; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            // 二分查找确定时间范围内的交易下标
            int left = 0, right = n - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (transactions[mid][0] >= start) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            int startIndex = left;
            left = 0;
            right = n - 1;
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                if (transactions[mid][0] <= end) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            int endInd

【华为OD机试】虚拟游戏理财（动态规划dp实现Java&Python&C++&JS）

评论已关闭

推荐阅读