2020CCPC威海(A Golden Spirit)

发布于 2020-10-31  0 次阅读


题目大意:

一座桥的两边分别有n个人,每个人都想到对面去休息t分钟,你需要将帮助所有人完成这件事,你带一个人带桥对面所耗费的时间为x
求最小的操作时间

Sample:

In:

3
2 2 2
3 1 10
11 45 14

Out:

16
120
616

思路:

考虑点:
将2n个老人都移动到各自的对面去后,假设我们最开始在左边,那么最后也应该在左边,
此时需要判断左边休息的最久的人(即为第一个从右到左的人)是否休息完成,
如果休息完成即可直接输出移动所有人的时间的两倍,即为2 ∗ 2 ∗ n ∗ t 22n*t2∗2∗n∗t(暂且即为总时间)。
如果没有休息完成,判断是在左边等待他休息完成还是去对面移动其他的老人
1、左边等待,在总时间上增加等待的时间即可
2、去右边,判断休息最早的人(即为第一次从左到右的人)休息完成否,
休息完成在总时间上加上过桥的时间,未完成在总时间加上过桥和等待他的时间

AC Code:

// #pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, x, t;
int sum, d1, d2;
void solve(){
    cin>>n>>x>>t;
    sum=2*n*t;      // 将所有人的位置交换需要的时间
    d2=sum-2*t;      // 第二个老人到对面的休息时间
    // 判断第二个老人此时是否休息完成
    if(d2>=x)   cout<<2*sum<<endl;
    else{
        // 选择等待第二个老人休息完成所消耗时间
        d2=2*sum + x-d2;
        d1=2*sum;
        // 到对面去判断第二个老人是否休息完成(此老人休息时间是sum+t-t)
        if(sum+t-t>=x)  d1+=t;          // 第一个老人休息完成,多需要的时间即为过桥的时间
        else            d1+=t+x-sum;    // 第二个老人为休息完成,多需要的时间为过桥和等待的时间
        cout<<mymin(d1,d2)<<endl;       // 输出两种情况需要的时间的最小值
    }   
	return ;
}

signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

平平无奇的大学在读本科生