poj 1700 Crossing River C++/Java

您所在的位置：网站首页 › POJ3253围栏修复问题JAVA › poj 1700 Crossing River C++/Java

poj 1700 Crossing River C++/Java

#poj 1700 Crossing River C++/Java| 来源: 网络整理| 查看: 265

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 #include 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=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=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); } } }

【本文地址】

poj 1700 Crossing River C++/Java

poj 1700 Crossing River C++/Java

今日新闻

推荐新闻