大同网站建设制作,门设计的网站建设,青岛房产信息网,秦皇岛建网站公司VJ链接
题意#xff1a;
河的两岸各有n个人#xff0c;中间有个桥#xff0c;过桥时间为t#xff0c;所有人过桥后要休息x时间#xff0c;你每次可以带一个人过桥#xff08;每次最多只能带一个人#xff09;#xff0c;问将所有人带到对岸并带回来#xff0c;最短需…VJ链接
题意
河的两岸各有n个人中间有个桥过桥时间为t所有人过桥后要休息x时间你每次可以带一个人过桥每次最多只能带一个人问将所有人带到对岸并带回来最短需要多少时间
题解
这题非常绕如果没有捋顺关系就会懵逼 最佳策略是带一个人到对岸后这个人要休息那我们就带另一个人到对岸相当于每次尽量带还没过桥的人当所有人第一轮带完后开始往回带此时我们所在一侧为起始位置而我们这一侧最早开始休息的人是第二次带的人对岸最早休息的人是第一次被带的人此时我们就考虑是过桥去对岸借第一个人还是在本岸等第二个人休息好再带过去。 这就有个比较 我们设 t1x-2ll*(n-1)t//表示第二次被带过岸的人还需要多久能休息好即本岸最早休息的人 t2x-(2lln-1)t//表示第一次被带过岸的人还需要多久能休息好即对岸最早休息的人 t是题目所给为过桥时间 x为休息时间 如果x(2lln-2)*t说明当第一轮带完之后所有人都休息好了此时无须等待直接再来一轮总时间为4nt即2n个人的过桥时间 如果t1max(t2,t)说明到去对岸接第一次过桥的人更划算 否则在原地等待第二次过桥的人更优 给个样例自己模拟模拟:
1
1 10 2ans16
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
int main()
{int t;cint;while(t--){ll n,x,t;cinnxt;ll t1x-2ll*(n-1)*t;ll t2x-(2ll*n-1)*t;if(x(2ll*n-2)*t)cout4ll*n*tendl;else if(t1max(t2,t)){cout4ll*n*tmax(t2,t)endl;}else coutt14ll*n*tendl;
// else if(x(2ll*n-1)*tt)cout4ll*n*t(x-(2ll*n-1)*t-t)endl;
// else coutx-(2ll*n-2)*t4ll*n*tendl;}return 0;
}
/*
1 2
2:|21
4:2|1*/