首页 > 代码库 > poj 1700 Crossing River C++/Java
poj 1700 Crossing River C++/Java
http://poj.org/problem?id=1700
题目大意:
有n个人要过坐船过河,每个人划船有个时间a[i],每次最多两个人坐一条船过河,且过河时间为两个人中速度慢的,求n个人过河的最短时间。
思路:
贪心。
对于每次过河的,有两种情况:
//最快和最慢过去,然后最快回来,在和次慢过去,最快回来 int action1=a[i-1] + a[0] + a[i-2] +a[0]; //最快和次慢过去,然后最快回来,在次慢和最慢过去,次慢回来 int action2=a[1] +a[0] + a[i-1] +a[1];
每次取最优即可。
#include<cstdio> #include<algorithm> using namespace std; const int MAXN=1024; int a[MAXN]; int main() { int T; scanf("%d",&T); while((T--)!=0) { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); int i; int ans=0; for(i=n;i>=4;i-=2) { //最快和最慢过去,然后最快回来,在和次慢过去,最快回来 int action1=a[i-1] + a[0] + a[i-2] +a[0]; //最快和次慢过去,然后最快回来,在次慢和最慢过去,次慢回来 int action2=a[1] +a[0] + a[i-1] +a[1]; ans=ans+ ( (action1 < action2 )? action1:action2); } if(i==3) ans+= a[0]+a[1]+a[2]; if(i==2) ans+=a[1]; if(i==1) ans+=a[0]; printf("%d\n",ans); } return 0; }
import java.util.Arrays; import java.util.Scanner; public class Main { public static int[] a=new int[1024]; public static void main(String[] args) { int T; Scanner in=new Scanner(System.in); T=in.nextInt(); while((T--)!=0) { int n=in.nextInt(); for(int i=0;i<n;i++) a[i]=in.nextInt(); Arrays.sort(a,0,n); int i; int ans=0; for(i=n;i>=4;i-=2) { //最快和最慢过去,然后最快回来,在和次慢过去,最快回来 int action1=a[i-1] + a[0] + a[i-2] +a[0]; //最快和次慢过去,然后最快回来,在次慢和最慢过去,次慢回来 int action2=a[1] +a[0] + a[i-1] +a[1]; ans=ans+ ( (action1 < action2 )? action1:action2); } if(i==3) ans+= a[0]+a[1]+a[2]; if(i==2) ans+=a[1]; if(i==1) ans+=a[0]; System.out.println(ans); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。