poj1700--贪心--Crossing River
2024-10-01 07:43:44
Crossing River
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 12260 | Accepted: 4641 |
Description
A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may
cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.
cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.
Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people
to cross the river. Each case is preceded by a blank line. There won't be more than 1000 people and nobody takes more than 100 seconds to cross.
to cross the river. Each case is preceded by a blank line. There won't be more than 1000 people and nobody takes more than 100 seconds to cross.
Output
For each test case, print a line containing the total number of seconds required for all the N people to cross the river.
Sample Input
1
4
1 2 5 10
Sample Output
17#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int cmp(int a,int b)
{
return a<b;
}
int main()
{
int t,s[1001];
scanf("%d",&t);
while(t--)
{
memset(s,0,sizeof(s));
int n,sum=0,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&s[i]);
sort(s,s+n,cmp);
for(i=n-1;i>2;i-=2)
{
if(s[0]*2+s[i]+s[i-1]>s[0]+s[1]*2+s[i])
sum+=s[0]+s[1]*2+s[i];
else sum+=s[0]*2+s[i]+s[i-1];
}
if(i==2) sum+=s[0]+s[1]+s[2];
if(i==1) sum+=s[1];
if(i==0) sum=s[0];
printf("%d\n",sum);
}
return 0;
}
最新文章
- 初次认识 C# win32 api
- JavaScript Date对象 日期获取函数
- Object-C : Block的实现方式
- css中的width,height,属性与盒模型的关系
- WordPress定位当前使用模版
- http keepalive
- 垃圾回收(GC)的三种基本方式
- java pdu短信解码
- 我的Jekyll博客
- SSH登陆服务器的简单命令
- MPSOC之4——petalinux提取源码
- 解决CUICatalog: Invalid asset name supplied问题
- java之web开发过滤器
- JDBC 异常简介 jDBC简介(六)
- IO通信模型(三)多路复用IO
- node.js 生成二维码
- Linux中DNS的设置
- 【Java】 剑指offer(34) 二叉树中和为某一值的路径
- linq时间筛选以及list时间筛选
- cinder创建volume的流程-简单梳理