POJ 2336 Ferry Loading II （贪心或动态规划）

链接：http://poj.org/problem?id=2336

贪心思想 --- 最早运到对岸的时间，取决于最后来的一辆车的被运送时间，因此最优解即是最后一辆车能够最早被运送；

解法：如果m%n == 0 则每次都运送n辆车，否则，第一次运送m%n辆车，然后接下来每次都运送n辆车；

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 1500
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int n, m, t, cas;

void solve()
{
    scanf("%d %d %d", &n, &t, &m);
    int L = m % n, k = m / n;
    int time_now, tr_times = k, return_time = 0;
    if(L) {
        tr_times++;
        for(int i=0; i<L; i++) {
            scanf("%d", &time_now);
            return_time = time_now + 2*t;
        }
    }
    for(int i=0; i<k; i++) {
        for(int j=0; j<n; j++) scanf("%d", &time_now);
        if(return_time >= time_now) return_time += 2*t;
        else return_time = time_now + 2*t;
    }
    printf("%d %d\n", return_time-t, tr_times);
}

int main(void)
{
    scanf("%d", &cas);
    while(cas--) solve();
}

POJ 2336 Ferry Loading II （贪心或动态规划）,布布扣,bubuko.com

POJ 2336 Ferry Loading II （贪心或动态规划）

原文：http://blog.csdn.net/keshacookie/article/details/23029587