首页 > 专题系列 > Java解POJ > POJ 2459 Feed Accounting [解题报告] Java
2013
11-11

POJ 2459 Feed Accounting [解题报告] Java

Feed Accounting

问题描述 :

Farmer John is trying to figure out when his last shipment of feed arrived. Starting with an empty grain bin, he ordered and received F1 (1 <= F1 <= 1,000,000) kilograms of feed. Regrettably, he is not certain exactly when the feed arrived. Of the F1 kilograms, F2 (1 <= F2 <= F1) kilograms of feed remain on day D (1 <= D <= 2,000). He must determine the most recent day that his shipment could have arrived.

Each of his C (1 <= C <= 100) cows eats exactly 1 kilogram of feed each day. For various reasons, cows arrive on a certain day and depart on another, so two days might have very different feed consumption. The input data tells which days each cow was present. Every cow ate feed from Farmer John's bin on the day she arrived and also on the day she left.

Given that today is day D, determine the minimum number of days that must have passed since his last shipment. The cows have already eaten today, and the shipment arrived before the cows had eaten.

输入:

* Line 1: Four space-separated integers: C, F1, F2, and D

* Lines 2..C+1: Line i+1 contains two space-separated integers describing the presence of a cow. The first integer tells the first day the cow was on the farm; the second tells the final day of the cow’s presence. Each day is in the range 1..2,000.

输出:

The last day that the shipment might have arrived, an integer that will always be positive.

样例输入:

3 14 4 10
1 9
5 8
8 12

样例输出:

6

温馨提示:

INPUT DETAILS:

The shipment was 14 kilograms of feed, and Farmer John has 4 kilograms left. He had three cows that ate feed for some amount of time in the last 10 days.

OUTPUT DETAILS:

If Farmer John started with 14 kg of feed on day 6, then on days 6 and 7, two kilograms would be eaten each day. On day 8, three kilograms would be eaten. On day 9, two kilograms would be eaten. On day 10, one kilogram would be eaten. Thus, the total eaten would be 2 + 2 + 3 + 2 + 1 = 10, leaving him with 4 kilograms.

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
 static final int N = 2000+10;
 static int DP[] = new int[N];
 public static void main(String[]args) throws Exception{
	int n,F1,F2,Day,i,sum,a,b,j;
	//Scanner cin = new Scanner(new FileInputStream("input.txt"));
	Scanner cin = new Scanner(System.in);
	n = cin.nextInt();
	F1 = cin.nextInt();
	F2 = cin.nextInt();
	Day = cin.nextInt();
	for(i=0;i< N;++i) DP[i] = 0;
	for(i=0;i< n;++i){
		a = cin.nextInt();
		b = cin.nextInt();
		for(j=a;j<=b;++j)
			++DP[j];
	}
	sum = 0;
	for(i=Day;i>=0;--i){
		sum+=DP[i];
		if(sum==F1-F2){
			System.out.println(i);
			break;
		}
	}
 }
}

  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。