2013
11-13

# Long Distance Racing

Bessie is training for her next race by running on a path that includes hills so that she will be prepared for any terrain. She has planned a straight path and wants to run as far as she can — but she must be back to the farm within M seconds (1 ≤ M ≤ 10,000,000).

The entire path she has chosen is T units (1 ≤ T ≤ 100,000) in length and consists of equal-length portions that are uphill, flat, or downhill. The input data describes path segment i with a single character Si that is u, f, or d, indicating respectively uphill, flat, or downhill.

Bessie takes U seconds (1 ≤ U ≤ 100) to run one unit of uphill path, F (1 ≤ F ≤ 100) seconds for a unit of flat path, and D (1 ≤ D ≤ 100) seconds for a unit of downhill path. Note that, when returning home, uphill paths become downhill paths and downhill paths become uphill paths.

Find the farthest distance Bessie can get from the farm and still make it back in time.

* Line 1: Five space-separated integers: M, T, U, F, and D
* Lines 2..T+1: Line i+1 describes path segment i with a single letter: Si

* Line 1: A single integer that is the farthest distance (number of units) that Bessie can get from the farm and make it back in time.

13 5 3 2 1
u
f
u
d
f


3


//* @author 洪晓鹏<[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */>
import java.util.Scanner;

public class Main {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int M = in.nextInt();
int T = in.nextInt();
int U = in.nextInt();
int F = in.nextInt();
int D = in.nextInt();
int num = 0;
int sum = 0;
for(int i = 0; i < T; i++)
{
String s = in.next();
if(sum > M)
break;
if(s.equals("u") || s.equals("d"))
sum += U + D;
else if(s.equals("f"))
sum += F + F;
num++;
}
System.out.println(num - 1);
}

}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

2. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;

3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

4. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧