2013
11-11

# POJ 2437 Muddy roads [解题报告] Java

Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools.

Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely.

Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools.

* Line 1: Two space-separated integers: N and L

* Lines 2..N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the start and end points of a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap.

* Line 1: The miminum number of planks FJ needs to use.

3 3
1 6
13 17
8 12


5


INPUT DETAILS:

FJ needs to use planks of length 3 to cover 3 mud pools. The mud pools cover regions 1 to 6, 8 to 12, and 13 to 17.

OUTPUT DETAILS:

FJ can cover the mud pools with five planks of length 3 in the following way:

                   111222..333444555....
.MMMMM..MMMM.MMMM....
012345678901234567890

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class POOL implements Comparable{
int left,right;
public int compareTo(Object oo){
POOL temp = (POOL) oo;
if(temp.left< this.left) return 1;
return -1;
}
}

public class Main {
static final int N = 10000+100;
static int n,L;
static POOL pool[] = new POOL[N];
static void start(){
for(int i=0;i< N;++i) pool[i] = new POOL();
}

public static void main(String[]args) throws Exception{
int i;
start();
StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

n = Get_Num(cin);
L = Get_Num(cin);
for(i=0;i< n;++i){
pool[i].left = Get_Num(cin);
pool[i].right = Get_Num(cin);
}
Arrays.sort(pool,0,n);
System.out.println(solve());

}

static int solve(){
int ans=0,cnt=0,i=0,j;
while(i< n){
if(pool[i].right>cnt-1){
j = (Min(pool[i].right-pool[i].left,pool[i].right-cnt)+L-1)/L;
cnt = Max(pool[i].left,cnt)+j*L;
ans+=j;
}
++i;
}
return ans;
}

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

static int Min(int a,int b){
return a< b?a:b;
}
static int Get_Num(StreamTokenizer cin) throws Exception{
cin.nextToken();
return (int) cin.nval;
}

}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

3. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
for (j = adj .begin(); j != adj .end(); ++j)
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？