https://cn.vjudge.net/problem/POJ-1201
题目
给定n个封闭整数区间[ai, bi]和n个整数c1,…cn。
编写一个程序:
读取区间数、它们的端点和整数c1,…, cn来自标准输入,
计算具有至少ci公共元素且区间为[ai, bi]的整数集Z的最小大小,对于每个i=1,2,…,n,
将答案写入标准输出。
Intervals
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.
Input
The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
分析
给定区间[a,b] 最多包含c哥点,求出交叉区间最少是多少个。
用一个res数组来记录改点是否记录并且是从终点向起点移动。

代码
package POJ;
import java.util.Scanner;
import static java.util.Arrays.sort;
public class _1201_Intervals {
static int n;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
Interval[] jobs = new Interval[n];
int max = -1;
for (int i = 0; i < n; i++) {
jobs[i] = new Interval(cin.nextInt(), cin.nextInt(), cin.nextInt());
}
sort(jobs);
max = jobs[n - 1].t;//排序过后最大的在最后 t是结束位置
int[] rec = new int[max + 1];//标记数轴上的点是否已标记
for (int i = 0; i < n; i++) {
int s = jobs[i].s;//起点
int t = jobs[i].t;//终点
int cnt = sum(rec, s, t);//找到这个区间已经选段的数量 sum[t]~sum[s-1]
jobs[i].c -= cnt;//需要点的数量
while ((jobs[i].c > 0)) {
if (rec[t] == 0) {//从终点开始选点
rec[t] = 1;
jobs[i].c--;//个数减少
t--;//终点左移
} else
t--;
}
}
System.out.println(sum(rec,0,max));
}
private static int sum(int[] rec, int s, int t) {
int sum = 0;
for (int i = s; i <= t; i++) {
sum += rec[i];
}
return sum;
}
public static class Interval implements Comparable<Interval> {
int s, t, c;
public Interval(int s, int t, int c) {
this.s = s;
this.t = t;
this.c = c;
}
@Override
public int compareTo(Interval o) {
int x = this.s - o.s;
if (x == 0) {
return this.t - o.t;
}
return x;
}
}
}
本文地址:https://dxoca.cn/Algorithm/243.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。