原题:http://poj.org/problem?id=2376
题目:问有N头牛,每头牛的工作时间不同,要工作T小时,最少需要几头牛工作。即是:输入 n 个区间和 t,接着输入 n 个区间[st, ed], 要求找出最少的区间数覆盖区间目标区间[1, t];
思路:先按开始时间从小到大、结束时间从大到小排序,然后再贪心。
代码:(AC)
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
/**
* poj2376
* @param args
*/
static class Cows{
int st;
int ed;
}
static Cows[] cows = new Cows[25001];
static int nNum ;
static int tLength ;
static int min_cow()
{
int count=1,j = 0;
int cur=cows[0].st,cur_len=cows[0].ed,i=0;
if(cur>1) return 0;
if(cur_len>=tLength) return 1;
while(i<nNum&&cur_len<tLength)
{
int max=0;
int tag=0;
while(i<nNum&&cows[i].st<=cur_len+1){
if(cows[i].ed>max){ max=cows[i].ed;j=i;
if(max>cur_len) tag=1;
}
i++;
}
i--;
if(tag==0) return 0;
cur_len=cows[j].ed;count++;
if(i==nNum-1&&cur_len<tLength) return 0;
}
return count;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext())
{
nNum = in.nextInt();
tLength = in.nextInt();
for(int i=0;i<nNum;i++)
{
cows[i] = new Cows();
cows[i].st = in.nextInt();
cows[i].ed = in.nextInt();
}
Arrays.sort(cows,0,nNum,new Comparator<Object>() {
public int compare(Object o1, Object o2) {
Cows a = (Cows)o1;
Cows b = (Cows)o2;
if(a.st<b.st)
return -1;
else if(a.st>b.st)
return 1;
else
{
if(a.ed<b.ed)
return 1;
else if(a.ed<b.ed)
return -1;
else
return 0;
}
};
});
int ans = min_cow();
if(ans!=0&&ans<=nNum)
System.out.println(ans);
else
System.out.println(-1);
}
}
}
分享到:
相关推荐
这是我发的第二篇解题报告,写的不怎么的。呵呵!!!!!
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告