By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：

参考：http://www.cppblog.com/cuijiaxing/archive/2010/08/18/123883.aspx

题目大意：

　　有一些汽车在左岸，你要用一条小破船把它们拉到右岸去。每个测试点包含多个测试数据。第一行的整数C表示测试数据的数目。接下来每个测试数据的
第一行为三个整数N, T, M表示一次可以运送N辆汽车，到达对岸的时间为T，汽车的总数是M。接下来的M行每行有一个整数，表示这辆汽车什么时候会来到左岸。对
于每个测试数据，输出两个整数，分别是最少要耗用多少时间（包括你等车的时间，就是从0开始直到最后一辆车到达右岸），以及在这个前提下你最少要运送多少
次。只要到右岸去就算作一次。

分析：

　　虽然看起来是用dp写的，但其实是基于贪心思想的，应该来说就是道贪心题。

  • 贪心策略：先运送M % N辆汽车到对岸（就是M除上N的余数），之后每次运N辆车，直到运完为止。最优解是最后一辆车能够一到达就被运送而不需要等了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))

int arr[1450];
int trip[1450];
int time[1450];
int n,t,m;
int main()
{
    int test;
    cin >> test;
    while(test--){
        cin >> n >> t >> m;
        for(int i = 1; i <= m; i++)
            scanf("%d",arr + i);
        trip[0] = time[0] = 0;

        sort(arr + 1, arr + m + 1);
        for(int j = 1; j <= m; j++)
        {
            time[j] = max(time[max(j-n,0)], arr[j]) + 2*t;
            trip[j] = trip[max(j-n,0)] + 1;//max(j-n,0)m小于n的都一次性载过河
        }
        printf("%d %d\n",time[m]-t,trip[m]);
    }
    return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：