poj-3404 Bridge over a rough river Ad Hoc
Bridge over a rough river
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 4427 | Accepted: 1824 |
Description
A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.
Each traveler needs ti seconds to cross the river on the bridge; i=1, ... , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.
The task is to determine minimal crossing time for the whole group.
Input
The input consists of two lines: the first line contains the value of N and the second one contains the values of ti (separated by one or several spaces).
Output
The output contains one line with the result.
Sample Input
4
6 7 6 5
Sample Output
29
Source
poj-3404
author:
Caution_X
date of submission:
20191010
tags:
Ad Hoc
description modelling:
n个人过桥,每个人过桥用时已给出,桥只能承载两个人,过河需要火炬,但是只有一个火炬,问最短过河时间
major steps to solve it:
1.两个人过桥之后需要有人把火炬送回来
2.以未过桥的四个人为一个单位,记为a,b,c,d其中a最快,b次快,c最慢,d次慢,分两种情况,①:每次都由最快的人把火炬送回来②:由最快帮助最慢过河,次快帮助次慢过河,步骤为a,b先过河,然后a回来,c,d一起过河,然后b回来带a过河
两种方式耗时为:①:2a+c+d ②:2b+a+c
3.每次以四人为单位选择过河方式直到剩下的人不足四人为止
warnings:
1.思维误区:容易认为方案一是唯一最有效方案
AC Code:
#include<cstdio>
#include<algorithm>
using namespace std;
int a[];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) {
scanf("%d",&a[i]);
}
if(n==) printf("%d\n",a[]);
else {
int ans=;
sort(a+,a+n+);
while(n>) {
if(a[]+a[n-]<*a[]) {
ans+=a[n]+a[]*+a[n-];
}
else {
ans+=a[]+a[]+a[]+a[n];
}
n-=;
}
if(n==) ans+=a[];
else ans+=a[]+a[]+a[];
printf("%d\n",ans);
}
return ;
}
最新文章
- 【C#】【Thread】Barrier任务并行
- Hadoop阅读笔记(七)——代理模式
- Day1 login
- 10 Useful du (Disk Usage) Commands to Find Disk Usage of Files and Directories
- 无奈卸载Clover 转投TotalCommand
- 数据库 mysql 优化器原理
- 开发RESTful WebService
- QF——iOS通知中心(NotificationCener)
- 手写js代码(一)javascript数组循环遍历之forEach
- Palindrome 回文数
- SocketServer源码学习(二)
- OO,OO以后,及其极限
- 使用Elasticsearch-dump迁移ES数据
- vue-cli +echarts-amap集成echarts和高德地图TypeError: Cannot read property &#39;dataToPoint&#39; of null解决方案
- react 入坑之罪
- pyCharm最新激活码(2018激活码)
- Grafana 安装及 Windows 应用程序服务配置工具 NSSM使用
- js滚动条如何缓慢的回到顶部?
- go 删除数组元素
- iOS之ProtocolBuffer搭建
热门文章
- RPA 可以给医疗行业带来哪些好处
- poj-3682 King Arthur&#39;s Birthday Celebration
- JAVA的基本语法1
- 易优CMS:小白学代码之notempty
- QML::Rectangle组件
- if语句,if...else语句的分析
- [转]Eclipse插件开发之基础篇(2) 第一个Eclipse插件
- Windows下使用ssh-add报错 Error connecting to agent: No such file or directory
- 安全类和远程类shell脚本
- nginx典型官方模块解释