2013
11-09

# 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.

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.

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.

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

6

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Intervals{
int left,right,ci;
}
public class Main {
static final int N = 50000+10;
static int DP[] = new int[N],n,left,right;
static Intervals Inter[] = new Intervals[N];

static void start(){
for(int i=0;i< N;++i)
Inter[i] = new Intervals();
}
static int Get_Num(StreamTokenizer cin) throws Exception{
if(cin.nextToken()==StreamTokenizer.TT_EOF)
return -1;
return (int) cin.nval;
}

static int solve(){
int i,j;
boolean flag=true;
for(i=left;i<=right;++i)
DP[i] = -N;
DP[left] = 0;
for(i=left;i<=right && flag;++i){
flag = false;
for(j=0;j< n;++j)if(DP[Inter[j].left]>-N && DP[Inter[j].left]+Inter[j].ci>DP[Inter[j].right]){
DP[Inter[j].right]= DP[Inter[j].left]+Inter[j].ci ;
flag = true;
}
for(j=left;j< right;++j) if(DP[j]>-N && DP[j]>DP[j+1]){
DP[j+1] = DP[j];
flag = true;
}
for(j=right;j>left;--j) if(DP[j]>-N && DP[j]-1>DP[j-1]){
DP[j-1] = DP[j]-1;
flag = true;
}
}
return DP[right];
}

public static void main(String[]args) throws Exception{
int i,j;
start();

while((n = Get_Num(cin))>0){
left = N ; right = 0;
for(i=0;i< n;++i){
Inter[i].left = Get_Num(cin);
Inter[i].right = Get_Num(cin)+1;
Inter[i].ci = Get_Num(cin);
left = Min(left,Inter[i].left);
right = Max(right,Inter[i].right);
}
System.out.println(solve());
}

}

static int Max(int a,int b){
return a>b?a:b;
}

static int Min(int a,int b){
return a< b?a:b;
}
}

1. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的