武昌做网站报价,西宁市公司网站建设,ysl免费网站建设,保定网站设计制作公司题干#xff1a;
题目大意#xff1a;
有N个人要过桥#xff0c;每个人速度不同#xff0c;只有一个手电筒#xff0c;每次最多只能过去两个人#xff0c;问所有人最短的过桥时间为多少
解题报告#xff1a; 首先让最快的两个人最后过#xff0c;然后我们分奇偶考虑…题干
题目大意
有N个人要过桥每个人速度不同只有一个手电筒每次最多只能过去两个人问所有人最短的过桥时间为多少
解题报告 首先让最快的两个人最后过然后我们分奇偶考虑分别处理到剩下三个人和两个人的情况。然后在做最后的处理。 除了最后的处理其实是最先执行的步骤我们看其他的步骤现在最快的俩人都在对岸。 现在两种贪心策略一个回合就处理两个人每个回合把当前速度最慢的两个人带到河岸 1.最快速度的人每次带一个当前速度最慢的人过去自己返回再带一个当前速度最慢的人过去 再返回也就是这俩最慢的都让最快的带回来 2.最快速度的人和速度第二快的人一起过去最快速的人返回速度最慢的两个人一起过去速度第二快的人返回。 对于每一个回合我们去这两种策略中的较小值贪心即可得到答案。 AC代码
//该死的格式错误怎么不提示PE了怎么成WA了
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int a[MAX];
int main()
{int t,n;cint;while(t--) {int ans 0;scanf(%d,n);for(int i 1; in; i) scanf(%d,ai);sort(a1,an1);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,time0;if(n%21) res3;else res2;for(int i n; ires; i-2) {ans a[1]a[i];//先跑过去 if(a[2]*2a[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; ires; 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%21) {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调回去这样代价肯定小了很多啊、、这里仅提供思路具体题目遇到再说、
