2023.04.19-暑期实习-第一题-塔子哥监考

TaZi SU @ 7 months ago

题目大意

塔子哥是一名监考机器人，能够同时监控多个考场。每个考场有不同的考试开始时间和结束时间。监控一个考场的费用是每分钟 3金币；监控两个或以上的考场时，费用是每分钟 4金币；如果没有监控任务，则每分钟消耗 1金币。要求计算塔子哥在一天的监考任务中能够获得多少金币。

思路

知识点学习:Oi-Wiki 前缀和&差分

题目意思本质为：一维正半轴上给 $n$ 条线段。每个整点 $i$ 有一个值 $v_i$ ，大小根据 $i$ 点覆盖的线段个数 $cover_i$ 来定.

$cover_i = 0 , v_i = 1$

$cover_i = 1 , v_i = 3$

$cover_i > 1 , v_i = 4$

然后求从最左边线段开始，到最右边线段结束这个区间的 $v_i$ 之和。

暴力做法

由于区间的范围有限，可以开数组 $cover[i]$ 。所以一个显然的暴力做法是:

1.枚举所有线段，循环让其覆盖的点 $cover[i]++$ .

2.最后扫一遍 $cover$ 数组，根据上述条件得到 $v_i$ 再求和即可。复杂度爆炸

优化

<暴力做法>中的第一步可以用差分数组解决：对于区间 $[l,r]$ , 我们 $cover[l]++,cover[r+1]--$ 。然后所有区间处理完之后，对 $cover$ 做前缀和 即可。 (可以自己纸上模拟这个过程体会一下原理)

代码说明

1.输入处理：

读取考场的数量 n，并记录每个考场的开始时间和结束时间。

2.初始化边界：

找到所有考场的最早开始时间和最晚结束时间，以便确定时间范围。

3.构建差分数组：

使用差分数组来表示每个时间点被监控的考场数量。对于每个考场的时间段 [a_i, b_i]，在 cover[a_i] 增加 1，cover[b_i + 1] 减少 1。

4.前缀和计算：

对差分数组进行前缀和计算，得到每个时间点的覆盖数量 cover[i]。

5.计算金币收入：

根据覆盖的数量计算在时间段内的收入。如果 cover[i] == 0，收入增加 1；如果 cover[i] == 1，收入增加 3；如果 cover[i] > 1，收入增加 4。

6.输出结果：

输出塔子哥在监考过程中的总收入。

差分数组

代码(C++/Java/Python/Go/Js)

CPP

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n; // 考场数量
    cin >> n; // 读取考场数量
    // 读入数据
    vector<vector<int>> lines(n, vector<int>(2)); // 存储每个考场的开始和结束时间
    int start = INT_MAX, end = INT_MIN; // 初始化最早开始时间和最晚结束时间
    // 获取最早开始时间和最晚结束时间
    for (int i = 0; i < n; i++) {
        cin >> lines[i][0] >> lines[i][1]; // 读取考场的开始和结束时间
        start = min(start, lines[i][0]); // 更新最早开始时间
        end = max(end, lines[i][1]); // 更新最晚结束时间
    }
    
    // 差分数组
    vector<int> cover(end + 2); // 创建差分数组，大小为最晚结束时间+2
    for (auto& line : lines) {
        cover[line[0]]++; // 在开始时间位置增加覆盖数量
        cover[line[1] + 1]--; // 在结束时间的下一个位置减少覆盖数量
    }
    
    // 前缀和
    for (int i = start; i <= end; i++) {
        if (i == 0) { // 如果时间为0，跳过不处理
            continue;
        }
        cover[i] += cover[i - 1]; // 计算前缀和，得到每个时间点的覆盖数量
    }
    
    // 根据题意计算金币收入
    int sum_v = 0; // 初始化收入总和
    for (int i = start; i <= end; i++) {
        if (cover[i] == 0) {
            sum_v += 1; // 如果没有覆盖，收入增加1金币
        } else if (cover[i] == 1) {
            sum_v += 3; // 如果只有一个考场被覆盖，收入增加3金币
        } else {
            sum_v += 4; // 如果两个或多个考场被覆盖，收入增加4金币
        }
    }
    
    cout << sum_v << endl; // 输出总收入
    return 0; // 程序结束
}

python

# 读取考场数量
n = int(input())

# 读取每个考场的开始和结束时间，并存储在列表中
lines = [list(map(int, input().split())) for i in range(n)]

# 获取最早开始时间和最晚结束时间
start = min([x[0] for x in lines])  # 找到所有考场的最早开始时间
end = max([x[1] for x in lines])    # 找到所有考场的最晚结束时间

# 创建差分数组，大小为最大结束时间+2
cover = [0] * (end + 2)  # 差分的右端点需要多一位

# 根据考场的开始和结束时间更新差分数组
for line in lines:
    cover[line[0]] += 1  # 在开始时间位置增加覆盖数量
    cover[line[1] + 1] -= 1  # 在结束时间的下一个位置减少覆盖数量

# 计算前缀和以获得每个时间点的覆盖数量
for i in range(start, end + 1):
    if i == 0:  # 如果时间为0，跳过
        continue
    cover[i] += cover[i - 1]  # 更新当前时间点的覆盖数量

# 根据覆盖数量计算金币收入
sum_v = 0  # 初始化收入总和
for i in range(start, end + 1):
    if cover[i] == 0:
        sum_v += 1  # 如果没有考场覆盖，收入增加1金币
    elif cover[i] == 1:
        sum_v += 3  # 如果只有一个考场被覆盖，收入增加3金币
    else:
        sum_v += 4  # 如果两个或多个考场被覆盖，收入增加4金币

# 输出总收入
print(sum_v)

Java

import java.util.Scanner; // 引入 Scanner 类，用于读取输入

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建 Scanner 对象
        int n = sc.nextInt(); // 读取考场数量

        int[][] lines = new int[n][2]; // 创建二维数组存储每个考场的开始和结束时间
        int start = Integer.MAX_VALUE; // 初始化最早开始时间为最大值
        int end = Integer.MIN_VALUE; // 初始化最晚结束时间为最小值

        // 获取最早开始时间和最晚结束时间
        for (int i = 0; i < n; i++) {
            lines[i][0] = sc.nextInt(); // 读取开始时间
            lines[i][1] = sc.nextInt(); // 读取结束时间
            start = Math.min(start, lines[i][0]); // 更新最早开始时间
            end = Math.max(end, lines[i][1]); // 更新最晚结束时间
        }

        int[] cover = new int[end + 2]; // 创建差分数组，大小为最大结束时间 + 2

        // 差分操作
        for (int[] line : lines) {
            cover[line[0]]++; // 在开始时间位置增加覆盖数量
            cover[line[1] + 1]--; // 在结束时间的下一个位置减少覆盖数量
        }

        // 前缀和
        for (int i = start; i <= end; i++) {
            if (i == 0) {
                continue; // 如果时间为 0，跳过不处理
            }
            cover[i] += cover[i - 1]; // 更新当前时间点的覆盖数量
        }

        // 根据题意计算金币收入
        int sum_v = 0; // 初始化收入总和
        for (int i = start; i <= end; i++) {
            if (cover[i] == 0) {
                sum_v++; // 如果没有覆盖，收入增加 1金币
            } else if (cover[i] == 1) {
                sum_v += 3; // 如果只有一个考场被覆盖，收入增加 3金币
            } else {
                sum_v += 4; // 如果两个或多个考场被覆盖，收入增加 4金币
            }
        }

        System.out.println(sum_v); // 输出总收入
        sc.close(); // 关闭 Scanner
    }
}

Go

package main

import (
	"bufio" // 引入 bufio 包，用于高效输入输出
	"fmt"   // 引入 fmt 包，用于格式化输入输出
	"math"  // 引入 math 包，用于数学计算
	"os"    // 引入 os 包，用于操作系统功能
)

const N = 1e6 + 10 // 定义常量 N，表示差分数组的大小

var n int // 考场数量

func main() {
	in := bufio.NewReader(os.Stdin) // 创建输入读取器
	out := bufio.NewWriter(os.Stdout) // 创建输出写入器
	defer out.Flush() // 在函数结束时刷新输出

	fmt.Fscan(in, &n) // 读取考场数量
	var start, end int // 定义开始和结束时间
	left, right := math.MaxInt32, math.MinInt32 // 初始化最早和最晚时间
	diff := make([]int, N) // 创建差分数组

	// 获取最早开始时间和最晚结束时间 + 差分
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &start, &end) // 读取每个考场的开始和结束时间
		left = min(left, start) // 更新最早开始时间
		right = max(right, end) // 更新最晚结束时间
		diff[start]++ // 在开始时间位置增加覆盖数量
		diff[end+1]-- // 在结束时间的下一个位置减少覆盖数量
	}

	ans, cur := 0, 0 // 初始化总收入 ans 和当前覆盖数量 cur
    // 前缀和 + 求和
	for i := 0; i <= right; i++ {
		cur += diff[i] // 计算当前时间点的覆盖数量
		if i >= left { // 只在有效时间范围内计算收入
			if cur == 0 {
				ans++ // 如果没有考场覆盖，收入增加 1金币
			} else if cur == 1 {
				ans += 3 // 如果只有一个考场被覆盖，收入增加 3金币
			} else {
				ans += 4 // 如果两个或多个考场被覆盖，收入增加 4金币
			}
		}
	}

	fmt.Fprintln(out, ans) // 输出总收入
}

// 辅助函数：返回较小的两个整数中的最小值
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// 辅助函数：返回较大的两个整数中的最大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Js

process.stdin.resume(); // 开始读取标准输入
process.stdin.setEncoding('utf-8'); // 设置输入编码格式为 UTF-8

let input = ""; // 用于存储输入数据
process.stdin.on("data", (data) => {
    input += data; // 将每次读取的数据追加到 input 中
});

// 定义求解函数
function solver(input) {
    let diffArr = new Array(1000000 + 2).fill(0); // 初始化差分数组，大小为 1000002
    let maxEnd = -1; // 初始化最大结束时间
    let minStart = 1000000 + 2; // 初始化最早开始时间

    // 处理每个时间区间
    for (let interval of input) {
        const [start, end] = interval.split(" "); // 读取开始时间和结束时间
        // 更新差分数组
        diffArr[parseInt(start)] += 1; // 在开始时间位置增加覆盖数量
        diffArr[parseInt(end) + 1] -= 1; // 在结束时间的下一个位置减少覆盖数量
        maxEnd = Math.max(parseInt(end), maxEnd); // 更新最大结束时间
        minStart = Math.min(parseInt(start), minStart); // 更新最早开始时间
    }

    let nowValue = 0; // 当前覆盖数量
    let count = 0; // 总收入初始化为 0
    for (let i = minStart; i <= maxEnd; i++) {
        // 前缀和计算
        nowValue += diffArr[i]; // 计算当前时间点的覆盖数量
        // 根据覆盖数量计算收入
        if (nowValue == 0) count += 1; // 如果没有覆盖，收入增加 1
        else if (nowValue == 1) count += 3; // 如果只有一个考场被覆盖，收入增加 3
        else count += 4; // 如果两个或多个考场被覆盖，收入增加 4
    } 
    return count; // 返回总收入
}

process.stdin.on("end", () => {
    const inputArr = input.split("\n"); // 按行分割输入
    const n = parseInt(inputArr[0]); // 读取考场数量
    const intervalArr = inputArr.slice(1, 1 + n); // 获取考场的时间区间
    console.log(solver(intervalArr)); // 调用求解函数并输出结果
});

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

前缀和

# Submissions

110

Accepted

Uploaded By

TaZi

1 solutions

题目大意

思路

暴力做法

优化

代码说明

差分数组

代码(C++/Java/Python/Go/Js)

CPP

python

Java

Go

Js

Information

Status

Development

Support