ACM 贪心 Crossing River

我就是我 2022-06-11 04:36 123阅读 0赞

滴，集训第十四天打卡。

台风终于来啦~

凉快了很多啊，但是湿漉漉的也很麻烦...

噫，好气。

**POJ 1700 Crossing River**

**![20170730164105170][]**

**题目大意：有N个人要渡河，但是只有一艘船，船上每次最多只能载两个人，渡河的速度由两个人中较慢的那个决定，（例如1和2一起过河，时间算2）小船来回载人直到所有人都渡河，求最短的渡河时间。**

**思路：这里详细讲一下样例，先sort一下，然后可以有两种情况过河。第一种是先12去，然后1回，然后5 10去，然后2回，然后12去。第二种是1 10去，然后1回，然后15去，然后1回，然后12去。所以当N为123的时候可以单独考虑，然后其他用上述的贪心即可。**

#include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int a[1005],i,t,n,sum;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            sum=0;
            for(i=0;i<n;i++)
            scanf("%d",&a[i]);
    		if(n==3)
            sum=a[0]+a[1]+a[2];
            else if(n==2)
            sum=a[1];
            else if(n==1)
            sum=a[0];
            else
            {
            	 while(n>3)
    	        {
    	            sum=min(sum+2*a[1]+a[0]+a[n-1],sum+a[n-1]+a[n-2]+2*a[0]);
    	            n-=2;
    	        }
            }       
            printf("%d\n",sum);
        }
    }

[20170730164105170]: /images/20220611/145f1628a1db4635aec7974004ce21be.png

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ - 1700 Crossing River

题目来源 [1700 -- Crossing River (poj.org)][1700 -- Crossing River _poj.org] 题目描述有N个

Myth丶恋晨/ 2023年09月26日 20:03/ 0 赞/ 123 阅读

相关【poj3258】River Hopscotch

![这里写图片描述][20160727174330784] ![这里写图片描述][20160727174339738] ![这里写图片描述][2016072717434

野性酷女/ 2022年09月24日 07:23/ 0 赞/ 73 阅读

相关 elasticsearch使用river同步mysql数据

====== mysql的river介绍====== - 什么是river？river代表es的一个数据源，也是其它存储方式（如：数据库）同步数据到es的一个方

布满荆棘的人生/ 2022年07月14日 10:23/ 0 赞/ 222 阅读

相关 ACM 贪心 Crossing River

滴，集训第十四天打卡。台风终于来啦~ 凉快了很多啊，但是湿漉漉的也很麻烦... 噫，好气。 POJ 1700 Crossing River ![2017073016

我就是我/ 2022年06月11日 04:36/ 0 赞/ 124 阅读

相关 ACM 贪心 Highway

滴，集训第九天打卡。感觉自己有些皮起来了，不是很有耐心做一些难题了... 今天的高效算法多是贪心做的。 UVA 1615 Highway ![201707251908

朱雀/ 2022年06月10日 23:41/ 0 赞/ 130 阅读

相关 poj-3258-River Hopscotch

River Hopscotch <table> <tbody> <tr> <td><strong>Time Limit:</strong> 200

深藏阁楼爱情的钟/ 2022年05月20日 06:53/ 0 赞/ 184 阅读

相关第六届河南省程序设计大赛——H River Crossing（简单动态规划）

题目描述: Afandi is herding N sheep across the expanses of grassland when he finds himsel

曾经终败给现在/ 2022年04月24日 23:12/ 0 赞/ 175 阅读

相关 elasticsearch-river-jdbc

整理下elasticsearch-river-jdbc插件的用法，希望对大家有帮助。环境：window + mysql 首先从介绍安装开始 1.1：es versio

不念不忘少年蓝@/ 2022年03月19日 08:36/ 0 赞/ 200 阅读

相关 cross apply

sqlserver中，用于一对多连接 inner join必须有on，写上关联条件 cross apply不需要on 要求：查询每个学生最近两次的考试成绩

￡神魔★判官ぃ/ 2022年01月31日 01:15/ 0 赞/ 197 阅读

相关 [Usaco2008 Mar]River Crossing渡河问题

题目描述 Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。由于奶牛不会划船，在整个渡河过程

你的名字/ 2021年12月24日 16:21/ 0 赞/ 262 阅读