首页 > 专题系列 > Java解POJ > POJ 1201 Intervals [解题报告] Java
2013
11-09

POJ 1201 Intervals [解题报告] Java

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();
  StreamTokenizer cin =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
  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
    不知道题目例子是怎么得出来的