在线评测链接:P1195 (opens new window)
# 题目内容
塔子哥是一个强大严厉的监考机器人,有他监考的考场总能抓到很多不不听话的学生,塔子哥”手眼通天“,能够同时仔细的观察很多考场,每个学生的一举一动他都能尽收眼底。
很多学校都想使用塔子哥监督考试,而塔子哥的使用成本也非常昂贵,当只监督一个考场时,每监视一分钟收费金币;同时监视两个以上的考场,每监视一分钟收费金币;当处于两个监考任务之间的空隙之间时,塔子哥会进入待机状态,每分钟消耗金币。也就是说,直到完成最后一个监考任务之前,塔子哥机器人都会持续消耗金币。
今天塔子哥又来监考,他今天一共要监视个不同的考场,每个考场的考试开始时间和结束时间都不同,为简化表达,将时间简化为整数代表的时间单位,时间从开始。
请你计算塔子哥今天的监考任务能够收取多少金币?
# 输入描述
第一行一个整数 表示塔子哥今天的监考考场数量
接下来 行,给出由空格分开的两个整数。表示 个考场考试的开始时间 与结束时间 ,也就是塔子哥开始监考与结束监考的时间(闭区间),保证结束时间大于起始时间
# 输出描述
一个整数,代表塔子哥今天监考所能赚取的金币
# 样例
输入
3
1 5
4 6
6 6
输出
21
# 思路
# 差分数组
知识点学习:Oi-Wiki 前缀和&差分 (opens new window)
题目意思本质为:一维正半轴上给条线段。每个整点有一个值,大小根据点覆盖的线段个数 来定.
然后求从最左边线段开始,到最右边线段结束这个区间的 之和。
# 暴力做法
由于区间的范围有限,可以开数组。所以一个显然的暴力做法是:
1.枚举所有线段,循环让其覆盖的点 .
2.最后扫一遍 数组,根据上述条件得到 再求和即可。复杂度爆炸
# 优化
<暴力做法>中的第一步可以用差分数组解决:对于区间 , 我们cover[l]++,cover[r+1]-- 。 然后所有区间处理完之后,对 做前缀和 即可。 (可以自己纸上模拟这个过程体会一下原理)
# 思考:O(1) 空间方法
可以不开 数组也求出 么?
# 类似题目推荐
# 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))
})