Ferry Loading||

uva10440:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1381

题意：题意：一条船能够一次最多渡n辆车过河，过河用t min，回来又要用t min。m辆车按照一定的计划到达岸边。现在要求最少

用多少时间就所有的船渡过河，以及用了最少多少次将所有。

题解：用贪心思想，最早运到对岸的时间，取决于最后来的一辆车的被运送时间，因此最优解就是最后一辆车能够最早被运送。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int cas,n,t,m,ll,train_timess,times;

 int map[];

 int main(){

     scanf("%d",&cas);

     while(cas--){

         scanf("%d%d%d",&n,&t,&m);

          for(int i=;i<=m;i++)

             scanf("%d",&map[i]);

         ll=m%n;train_timess=;times=;

         if(ll==){

             train_timess=m/n;

             for(int i=n;i<m;i+=n){

                 times=max(map[n],times)+*t;

             }

             times=max(map[m],times)+t;

         }

         else{train_timess=m/n+;

             times=map[ll]+*t;

             for(int i=ll+n;i<m;i+=n){

                 times=max(times,map[i])+*t;

             }

             times=max(map[m],times)+t;

         }

         printf("%d %d\n",times,train_timess);

     }

 }

巴特西

Ferry Loading||

最新文章

热门文章