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); }
}
上一篇:Qt XML的使用


下一篇:@Secured(), @PreAuthorize()