在线评测链接:P1195 (opens new window)

题目内容

塔子哥是一个强大严厉的监考机器人，有他监考的考场总能抓到很多不不听话的学生，塔子哥”手眼通天“，能够同时仔细的观察很多考场，每个学生的一举一动他都能尽收眼底。

很多学校都想使用塔子哥监督考试，而塔子哥的使用成本也非常昂贵，当只监督一个考场时，每监视一分钟收费$3$金币；同时监视两个以上的考场，每监视一分钟收费$4$金币；当处于两个监考任务之间的空隙之间时，塔子哥会进入待机状态，每分钟消耗$1$金币。也就是说，直到完成最后一个监考任务之前，塔子哥机器人都会持续消耗金币。

今天塔子哥又来监考，他今天一共要监视$n$个不同的考场，每个考场的考试开始时间和结束时间都不同，为简化表达，将时间简化为整数代表的时间单位，时间从$0$开始。

请你计算塔子哥今天的监考任务能够收取多少金币？

输入描述

第一行一个整数 $n$ 表示塔子哥今天的监考考场数量

接下来 $n$ 行，给出由空格分开的两个整数$a_i, b_i$。表示 $n$ 个考场考试的开始时间 $a_i$ 与结束时间 $b_i$ ，也就是塔子哥开始监考与结束监考的时间（闭区间），保证结束时间大于起始时间

$1 \leqslant n \leqslant 10000$

$0 \leqslant a_i,b_i \leqslant 10^6$

输出描述

一个整数，代表塔子哥今天监考所能赚取的金币

样例

输入

3
1 5
4 6
6 6

输出

21

思路

差分数组

知识点学习:Oi-Wiki 前缀和&差分 (opens new window)

题目意思本质为：一维正半轴上给$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$ 做前缀和 即可。 (可以自己纸上模拟这个过程体会一下原理)

思考:O(1) 空间方法

可以不开$cover$ 数组也求出$v_i$ 么？

类似题目推荐

LeetCode

1109. 航班预订统计 (opens new window)

1526. 形成目标数组的子数组最少增加次数 (opens new window)

CodeFun2000

P1078 2023.3.11-美团春招-第二题-天文爱好者 (opens new window)

代码

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);
    for (auto& line : lines) {
        cover[line[0]]++;
        cover[line[1] + 1]--;
    }
    // 前缀和
    for (int i = start; i <= end; i++) {
        if (i == 0) {
            continue;
        }
        cover[i] += cover[i - 1];
    }
    // 根据题意v求和
    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;
        } else {
            sum_v += 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])
cover = [0] * (end + 2) # 差分的右端点需要多一位 , 所以是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:
        continue
    cover[i] += cover[i - 1]
sum_v = 0
for i in range(start , end + 1):
    if cover[i] == 0:
        sum_v += 1
    elif cover[i] == 1:
        sum_v += 3
    else:
        sum_v += 4
print(sum_v)

Java

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        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];
		// 差分
        for (int[] line : lines) {
            cover[line[0]]++;
            cover[line[1] + 1]--;
        }
		// 前缀和
        for (int i = start; i <= end; i++) {
            if (i == 0) {
                continue;
            }
            cover[i] += cover[i - 1];
        }
		// 根据题意求和
        int sum_v = 0;
        for (int i = start; i <= end; i++) {
            if (cover[i] == 0) {
                sum_v++;
            } else if (cover[i] == 1) {
                sum_v += 3;
            } else {
                sum_v += 4;
            }
        }

        System.out.println(sum_v);
        sc.close();
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

const N = 1e6 + 10

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
    // 前缀和 + 求和
	for i := 0; i <= right; i++ {
		cur += diff[i]
		if i >= left {
			if cur == 0 {
				ans++
			} else if cur == 1 {
				ans += 3
			} else {
				ans += 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')


let input = ""
process.stdin.on("data", (data) => {
    input += data
})

function solver(input){
    let diffArr = new Array(1000000+2).fill(0)
    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
    for(let i = minStart; i<=maxEnd; i++){
        // 前缀和
        nowValue += diffArr[i]
        // 求和
        if(nowValue == 0) count += 1
        else if(nowValue == 1) count += 3
        else  count += 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)) 
})