题面描述

在一条笔直的公路上安装了 $N$ 个路灯，从位置 $0$ 开始安装，路灯之间间距固定为 $100$ 米。

每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和。

思路

要计算第一个路灯和最后一个路灯之间无法照明的区间长度和，我们可以按照以下步骤进行：

1. 确定路灯位置：

   • 第 $i$ 个路灯的位置为 $(i-1) \times 100$ 米，其中 $i$ 从 $1$ 到 $N$。

2. 计算每个路灯的覆盖区间：

   • 每个路灯的覆盖区间为 $[位置 - 半径, 位置 + 半径]$。
   • 由于我们只关心第一个路灯和最后一个路灯之间的区间，即 $0$ 到 $(N-1) \times 100$ 米，因此需要将每个覆盖区间限制在这个范围内。

3. 合并所有覆盖区间：

   • 将所有覆盖区间按起点排序。
   • 依次遍历这些区间，合并重叠或相邻的区间，得到一组不重叠的覆盖区间。

4. 计算未覆盖的总长度：

   • 总的考察区间长度为 $(N-1) \times 100$ 米。
   • 计算所有合并后的覆盖区间的总长度。
   • 未覆盖的长度为总考察区间长度减去覆盖区间的总长度。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 定义一个结构体表示区间
struct Interval {
    ll start;
    ll end;
};

// 比较函数，用于按起点排序
bool cmp(const Interval &a, const Interval &b) {
    if (a.start != b.start)
        return a.start < b.start;
    return a.end < b.end;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll N;
    cin >> N;
    vector<ll> radii(N);
    for(auto &x: radii) cin >> x;
    
    // 计算考察区间范围
    ll left = 0;
    ll right = (N-1)*100;
    
    vector<Interval> intervals;
    intervals.reserve(N);
    
    for(ll i=0; i<N; ++i){
        ll pos = i * 100;
        ll l = max(left, pos - radii[i]);
        ll r = min(right, pos + radii[i]);
        if(l > right || r < left) continue; // 不在考察区间内
        intervals.push_back(Interval{l, r});
    }
    
    if(intervals.empty()){
        // 没有任何覆盖
        cout << (right - left) << "\n";
        return 0;
    }
    
    // 按起点排序
    sort(intervals.begin(), intervals.end(), cmp);
    
    // 合并区间
    vector<Interval> merged;
    merged.reserve(N);
    merged.push_back(intervals[0]);
    
    for(int i=1; i<intervals.size(); ++i){
        if(intervals[i].start <= merged.back().end){
            // 有重叠，合并
            merged.back().end = max(merged.back().end, intervals[i].end);
        }
        else{
            // 无重叠，加入新的区间
            merged.push_back(intervals[i]);
        }
    }
    
    // 计算覆盖总长度
    ll covered = 0;
    for(auto &iv: merged){
        covered += (iv.end - iv.start);
    }
    
    // 计算未覆盖长度
    ll total = right - left;
    ll uncovered = total - covered;
    cout << uncovered << "\n";
}

python

import sys

def main():
    import sys
    import sys
    N_and_rest = sys.stdin.read().split()
    N = int(N_and_rest[0])
    radii = list(map(int, N_and_rest[1:N+1]))
    
    left = 0
    right = (N-1)*100
    
    intervals = []
    for i in range(N):
        pos = i * 100
        l = max(left, pos - radii[i])
        r = min(right, pos + radii[i])
        if l > right or r < left:
            continue
        intervals.append( (l, r) )
    
    if not intervals:
        print(right - left)
        return
    
    # 按起点排序
    intervals.sort()
    
    # 合并区间
    merged = []
    current_start, current_end = intervals[0]
    for l, r in intervals[1:]:
        if l <= current_end:
            current_end = max(current_end, r)
        else:
            merged.append( (current_start, current_end) )
            current_start, current_end = l, r
    merged.append( (current_start, current_end) )
    
    # 计算覆盖总长度
    covered = sum( end - start for start, end in merged )
    
    # 计算未覆盖长度
    total = right - left
    uncovered = total - covered
    print(uncovered)

if __name__ == "__main__":
    main()

java

import java.io.*;
import java.util.*;

public class Main {
    static class Interval implements Comparable<Interval>{
        long start, end;
        Interval(long s, long e){
            start = s;
            end = e;
        }
        public int compareTo(Interval other){
            if(this.start != other.start){
                return Long.compare(this.start, other.start);
            }
            return Long.compare(this.end, other.end);
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long[] radii = new long[(int)N];
        for(int i=0; i<N; i++) radii[i] = Long.parseLong(st.nextToken());
        
        long left = 0;
        long right = (N-1)*100;
        
        ArrayList<Interval> intervals = new ArrayList<>();
        for(int i=0; i<N; i++){
            long pos = i * 100;
            long l = Math.max(left, pos - radii[i]);
            long r = Math.min(right, pos + radii[i]);
            if(l > right || r < left) continue;
            intervals.add(new Interval(l, r));
        }
        
        if(intervals.isEmpty()){
            System.out.println(right - left);
            return;
        }
        
        Collections.sort(intervals);
        
        ArrayList<Interval> merged = new ArrayList<>();
        Interval current = intervals.get(0);
        for(int i=1; i<intervals.size(); i++){
            Interval next = intervals.get(i);
            if(next.start <= current.end){
                current.end = Math.max(current.end, next.end);
            }
            else{
                merged.add(current);
                current = next;
            }
        }
        merged.add(current);
        
        long covered = 0;
        for(Interval iv : merged){
            covered += (iv.end - iv.start);
        }
        
        long total = right - left;
        long uncovered = total - covered;
        System.out.println(uncovered);
    }
}

题目描述

在一条笔直的公路上安装了 $N$ 个路灯，从位置 $0$ 开始安装，路灯之间间距固定为 $100$ 米。

每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和。

输入描述

第一行为一个数 $N$ ，表示路灯个数，$1<=N<=100000$

第二行为 $N$ 个空格分隔的数，表示路灯的照明半径，$1<=$照明半径$<=100000*100$

输出描述

第一个路灯和最后一个路灯之间，无法照明的区间的长度和

样例1

输入

2
50 50

输出

0

说明

路灯 $1$ 覆盖 $0-50$ ，

路灯 $2$ 覆盖 $50-100$ ，

路灯 $1$ 和路灯 $2$ 之间($0$米-$100$米)无未覆盖的区间。

样例2

输入

4
50 70 20 70

输出

20

说明

路灯$1$ 覆盖$0-50$

路灯$2$ 覆盖$30-170$

路灯$3$ 覆盖$180-220$

路灯$4$ 覆盖$230-370$

$[170,180]$,$[220,230]$，两个未覆盖的区间，总里程为 $20$