3998622_re.java

北大大牛代码 1240道题的原代码 超级权威

package p1919;

import java.io.FileInputStream;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

	private Scanner in;
	private LinkedList<DriftInfo> driftinfo;
	private int d;
	private double deadline;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}

	class DriftInfo implements Comparable<DriftInfo> {

		int time;
		double speed;

		public DriftInfo() {
			time = in.nextInt();
			speed = in.nextDouble() + 10.0;
		}

		public DriftInfo(int time, double speed) {
			this.time = time;
			this.speed = speed;
		}

		public int compareTo(DriftInfo that) {
			return this.time - that.time;
		}
	}

	private void run() {
		// TODO Auto-generated method stub
		try {
			//in = new Scanner(new FileInputStream("C:\\elbefahrt.tin"));
			in = new Scanner(System.in);
		} catch (Exception e) {
		}
		
		int cas;

		cas = in.nextInt();
		while (cas-- != 0) {
			deadline = in.nextDouble();
			d = in.nextInt();
			driftinfo = new LinkedList<DriftInfo>();
			for (int i = 0; i < d; i++) {
				driftinfo.add(new DriftInfo());
			}
			Collections.sort(driftinfo);
			if (driftinfo.get(0).time > 0) {
				driftinfo.addFirst(new DriftInfo(0, 10));
			}
			driftinfo.addLast(new DriftInfo(10000000, 10));
			d = driftinfo.size();
			double mintime = 1000000000.0;
			int besttime = -1;
			for (int starttime = 50; starttime < deadline; starttime++) {
				double time = calc(starttime);
				if (time != -1 && time <= mintime) {
					mintime = time;
					besttime = starttime;
				}
			}
			System.out.println(besttime);
		}
	}

	private double calc(int starttime) {
		// TODO Auto-generated method stub
		int st = -1;

		for (int i = 0; i < d; i++) {
			if (driftinfo.get(i).time > starttime) {
				st = i;
				break;
			}
		}
		assert (st > 0) : "Impossible";
		double time = 0.0;
		int last = starttime;
		double distance = 0.0;
		while (true) {
			double tmp = driftinfo.get(st - 1).speed
					* (driftinfo.get(st).time - last) * 1000.0 / 60.0;
			if (distance + tmp >= 100000.0) {
				time += (100000.0 - distance) / driftinfo.get(st - 1).speed * 60.0 / 1000.0;
				break;
			}
			distance += tmp;
			time += driftinfo.get(st).time - last;
			last = driftinfo.get(st).time;
			st++;
		}
		if (starttime + time >= deadline) {
			return -1;
		}
		return time;
	}
}