【UVA - 10037】Bridge（过河问题，经典贪心）,金山wps2012

文件名：【UVA - 10037】Bridge（过河问题，经典贪心）,金山wps2012 【UVA - 10037】Bridge（过河问题，经典贪心）

题干：

题目大意：

有N个人要过桥，每个人速度不同，只有一个手电筒，每次最多只能过去两个人，问所有人最短的过桥时间为多少

解题报告：

  首先让最快的两个人最后过，然后我们分奇偶考虑，分别处理到剩下三个人和两个人的情况。然后在做最后的处理。

  除了最后的处理（其实是最先执行的步骤），我们看其他的步骤，现在最快的俩人都在对岸。

   现在两种贪心策略：（一个回合就处理两个人，每个回合把当前速度最慢的两个人带到河岸）

      1.最快速度的人每次带一个当前速度最慢的人过去，自己返回；再带一个当前速度最慢的人过去， 再返回（也就是这俩最慢的都让最快的带回来）

      2.最快速度的人和速度第二快的人一起过去；最快速的人返回，速度最慢的两个人一起过去；速度第二快的人返回。

    对于每一个回合，我们去这两种策略中的较小值，，贪心即可得到答案。

         

AC代码：

//该死的格式错误怎么不提示PE了？？怎么成WA了？？？？#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define ll long long#define pb push_back#define pm make_pair#define fi first#define se secondusing namespace std;const int MAX = 2e5 + 5;int a[MAX];int main(){int t,n;cin>>t;while(t--) {int ans = 0;scanf("%d",&n);for(int i = 1; i<=n; i++) scanf("%d",a+i);sort(a+1,a+n+1);if(n == 1) {printf("%d\n%d\n",a[1],a[1]);if(t) puts("");continue;}if(n == 2) {printf("%d\n%d %d\n",a[2],a[1],a[2]);if(t) puts("");continue;}int res,time=0;if(n%2==1) res=3;else res=2;for(int i = n; i>res; i-=2) {ans += a[1]+a[i];//先跑过去 if(a[2]*2<a[i-1]+a[1]) ans += a[2] + a[2];else ans += a[i-1]+a[1];}if(n%2 == 1) ans += a[1]+a[2]+a[3];else ans += a[2];printf("%d\n",ans);if(n == 3) {printf("%d %d\n%d\n",a[1],a[2],a[1]);printf("%d %d\n",a[1],a[3]);if(t) puts("");continue;}for(int i = n; i>res; i-=2) {if(a[2]*2 < a[i-1]+a[1]) {printf("%d %d\n%d\n", a[1], a[2], a[1]);printf("%d %d\n%d\n", a[i-1], a[i], a[2]);}else {printf("%d %d\n%d\n", a[1], a[i-1], a[1]);printf("%d %d\n%d\n", a[1], a[i], a[1]);}}if(n%2==1) {printf("%d %d\n%d\n", a[1], a[2], a[1]);printf("%d %d\n", a[1], a[3]);}else printf("%d %d\n",a[1],a[2]);if(t) puts("");} return 0 ;}

  就像学长说的，这题重要的是这个贪心的思路，可以构造出很多不同的题型：比如学长讲课时说的，可以和置换群建立起关系。比如构造一个题：

     给你n个数（数值保证从1~n 且互不相同），先定义一种操作：可以任选两个元素进行交换，交换的代价是这两个元素值的和。现在问你如果我要吧这个序列变成一个有序序列，最小的代价是多少。

   首先我们知道，我们要找一些轮换，然后这一些轮换对调就可以了，根据置换群的知识，我们知道可以把这些对调换成一个个的对换去完成，并且如果这一个轮换涉及k个元素的话，我们需要对换k-1次，那么既然次数确定，并且需要有一个作为每次都出现的（详情见离散数学），那我们就贪心那个最小的作为每一次对换都出现的元素，，这一点并不难想。。但是有没有可能有更优的选择？比如我们(100,102,104,103,105,106,107,108)这有八个元素组成一个轮换的话（顺序是我瞎写的）那我们肯定选100当那个每次都出现在对换中的元素，，但是我们想，有没有可能把另外一个最小的元素换过来当成最小的元素，换完了以后再换回去呢？比如还有一个轮换(1,2,3)，那么我们先1和100对调，然后再用1去做那7次对换，然后再把1和100调回去，这样代价肯定小了很多啊、、这里仅提供思路，，具体题目遇到再说、