3998700_wa.cpp

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

/* TU Darmstadt Programming Contest 2001
 * Problem: Ship Journey
 * Author : Felix Gaertner
 * Comment: converted Java solution
 */

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

#define LENGTH 100   /* total length in km */
#define MINPH 60     /* minuted per hour */
#define NORMSPEED 10 /* normal speed in km/h */
#define INFINITY 999999  /* trip time will not exceed this value */

/* forwards */
void do_scenario(void);
float trip_duration(int, int, int[], int[], int);


int main(void) {

    int scenarios = 0, n;
    
    
    n = scanf("%d", &scenarios);
    assert(scenarios>0);

    while (scenarios--) {
	do_scenario();
	//scenarios--;
    }

    return 0;
}

void do_scenario() {

    int n, i, time;
    float arrival;

    /* latest arrival in minutes: */
    int la = 0;
    /* number of data sets: */
    int ds = 0;
    /* store for data sets */
    int* m;
    int* s;
    
    /* minimum trip duration */
    float minimum = INFINITY;
    /* starting time for that duration */
    int opttime = 0;           



    n = scanf("%d", &la);
    assert(n==1);
    n = scanf("%d", &ds);
    assert(n==1);

    m = (int*) (malloc(sizeof(int)*ds));
    assert(m!=NULL);
    s = (int*) (malloc(sizeof(int)*ds));
    assert(s!=NULL);


    for (i=0; i<ds; i++) {
	/* read and parse next line to m and s */
	n = scanf("%d", &m[i]);
	assert(n==1);
	n = scanf("%d", &s[i]);
	//fprintf(stderr, "read m=%d, s=%d\n", m[i], s[i]);
    }
    assert(m[0]==0);


    /* brute force: test all possible departure times: */

    for (time=0; time<=la; time++) {
	float t = trip_duration(time, ds, m, s, la);
	//fprintf(stderr, "duration starting at %d is %f\n", time, t);
	if ((t<=minimum) && (t+time < la)) {
	    //fprintf(stderr, "Found new minimal solution at starting time %d\n", time);
	    minimum = t;
	    opttime = time;
	}
    }

    /* hier runden! */
    arrival = opttime + minimum;

    if (minimum == INFINITY) {
	printf("bad input data: no solution possible\n");
    } else {
	printf("%d\n", opttime);
    }

    /* cleanup */
    free(m);
    free(s);
}


/* ds gives size of m and s */
float trip_duration(int t, int ds, int m[], int s[], int la) {
	
    int lc = t;      /* last change of speed */
    float cv = NORMSPEED;   /* current velocity (speed) */
    float km = 0;    /* km travelled */
    int dsptr = 0;   /* data set pointer */

    //fprintf(stderr, "Testing time %d\n", t);
    /* assumption: m and s have same length */
    
    //fprintf(stderr, "Starting at km %d\n", km);
    //fprintf(stderr, "Length to go (km): %d\n", LENGTH);
    //fprintf(stderr, "Normal speed (km/h): %d\n", NORMSPEED);
    //fprintf(stderr, "Minutes per hour: %d\n", MINPH);

    while ((dsptr < ds) && (m[dsptr] <= t)) {
	//fprintf(stderr, "skipping %d m=%d, adjusting speed=%d\n", 
	//	dsptr, m[dsptr], s[dsptr]);
	cv = NORMSPEED + s[dsptr];
	dsptr++;
    }
		
    if (dsptr>=ds) {
	//fprintf(stderr, "Trivial solution\n");
	return ((LENGTH/cv)*MINPH);
    } else {
	/* remaining minutes at current speed */
	float rm = ((LENGTH - km) / cv) * MINPH;
	//fprintf(stderr, "%d: remaining min @ current speed: %f\n", lc, rm);

	while (rm > m[dsptr]) {
	    /* sum up km travelled between changes */
	    km += ( m[dsptr] - lc ) * cv / (float) MINPH;
	    //fprintf(stderr, "now at km %f\n", km);
	    /* calculate new speed */
	    cv = NORMSPEED + s[dsptr];
	    /* store min of last change */
	    lc = m[dsptr];
			
	    if (dsptr < ds-1) {  /* still info to process? */
		dsptr++;
		//fprintf(stderr, "looking at %d m=%d, s=%d\n", 
		//	dsptr, m[dsptr], s[dsptr]);
	    } else {
		//fprintf(stderr, "Finished testing %d\n", t);
		break;
	    }

	    rm = ((LENGTH - km) / cv) * MINPH;
	    //fprintf(stderr, "%d: remaining min @ current speed: %f\n", lc, rm);
	}

	return (lc - t + rm);
    }
}