寒光博客

[ POJ]1201 Intervals 区间选点问题 贪心策略
https://cn.vjudge.net/problem/POJ-1201 题目 给定n个封闭整数区间[ai, ...
扫描右侧二维码阅读全文
12
2019/08

[ POJ]1201 Intervals 区间选点问题 贪心策略

https://cn.vjudge.net/problem/POJ-1201

题目

给定n个封闭整数区间[ai, bi]和n个整数c1,…cn。
编写一个程序:
读取区间数、它们的端点和整数c1,…, cn来自标准输入,
计算具有至少ci公共元素且区间为[ai, bi]的整数集Z的最小大小,对于每个i=1,2,…,n,
将答案写入标准输出。

Intervals

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数组来记录改点是否记录并且是从终点向起点移动。

若要代码 ac 需要求区间和 (数组前缀和)用树状数组解决 以下的贪心策略

代码

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;
        }
    }
}
本文作者:Author:     文章标题:[ POJ]1201 Intervals 区间选点问题 贪心策略
本文地址:https://dxoca.cn/Algorithm/243.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 12th, 2019 at 06:56 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment