第二周--贪心题解（W）

题W Before bridges were common, ferries were used to transport cars across rivers. River ferries, unlike their larger cousins, run on a guide line and are powered by the river’s current. Cars drive onto the ferry from one end, the ferry crosses the river, and the cars exit from the other end of the ferry. There is a ferry across the river that can take n cars across the river in t minutes and return in t minutes. m cars arrive at the ferry terminal by a given schedule. What is the earliest time that all the cars can be transported across the river? What is the minimum number of trips that the operator must make to deliver all cars by that time? Input The first line of input contains c, the number of test cases. Each test case begins with n, t, m. m lines follow, each giving the arrival time for a car (in minutes since the beginning of the day). The operator can run the ferry whenever he or she wishes, but can take only the cars that have arrived up to that time. Output For each test case, output a single line with two integers: the time, in minutes since the beginning of the day, when the last car is delivered to the other side of the river, and the minimum number of trips made by the ferry to carry the cars within that time.

You may assume that 0 < n, t, m < 1440. The arrival times for each test case are in non-decreasing order. Sample Input 2 2 10 10 0 10 20 30 40 50 60 70 80 90 2 10 3 10 30 40 Sample Output 100 5 50 2

题意：由于桥并没有得到普及，用轮渡将需要过河的车进行运输。每个车都有到达河岸的时间m，轮渡每趟能运输n辆车，每次运过去要t分钟，运回来也要t分钟。问，将所有车运到河另一侧的时间（注意不是轮渡最后一趟回来的时间）以及轮渡需要运输的趟数（注意也不是来回的次数，最后一次只去不会）。

思路： 1.难点之一就是理解题目的背景，正确把握题意，然后转化为贪心问题求解。 2.趟数非常容易求解，用需要运输的车辆除以轮渡容量即可，若有余数则进1。但要明白这里是题目的突破口，是为了得到最后时间，题目给出的提示。引导你将时间折合成趟数进行思考。 3.如果m%n不为0，那么将最后一趟的时间单独拎出来算，也就等效与将前几个数（个数等于余数）先用轮渡拉走，后面的车辆正好能整除n，然后趟数便只是m/n，每趟的时间为2t累加，最后减去一个t即可。偶数不需要单独考虑。 4.需要注意，当轮渡回来时，要和t的倍数到达的车辆时间相比较，若大于则直接拉走，若小于则需要等待车辆到达。时间更新为到达的时间。

代码：

#include 
#include
#include
#include
#include

using namespace std;
int a[1445];

int main()
{
    int c;
    cin>>c;
    while(c--)
    {
        int n,t,m;
        cin>>n>>t>>m;
        for(int i=0;i>a[i];
        }
        sort(a,a+m);
        int l=m%n;
        int s=m/n;
        int k,time=0;
        if(l) k=s+1;
        else k=s;
        if(l) time=a[l-1]+2*t;
        int j=1;
        while(j=a[j*n+l-1])
            {
                time+=2*t;
                if(j==s) time-=t;
            }
            else
            {
                time=a[j*n+l-1];
                time+=2*t;
                if(j==s) time-=t;
            }

           j++;
        }
        cout