A. Line Trip

题意：

有一条路，从0到x，你需要开汽车从0到x再返回0，每个单位距离消耗一升油，出发时汽车满油，中间设有n个加油站，求油箱的最小容积

思路：

油箱中的油至少要能坚持从一个加油站开到下一个加油站，注意最后一个加油站到达x后需要往返回到最后一个加油站

代码：

#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"

void solve(){
	int n,x;
    cin>>n>>x;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    a[0]=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,a[i]-a[i-1]);
    }
    ans=max(ans,2*(x-a[n]));
    cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

B. Chip and Ribbon

题意：

给定n个单元格，有一个芯片第一轮在位置1，每一轮可以做以下两个操作中的一个：将芯片移动到下一位；将芯片传送到任意一个位置。每次操作后那个位置的数值加一，最终数值大小和数组c一致，求最小传送次数

思路：

若c[i]>c[i+1]，则可以在操作完位置i后移动到i+1使位置i+1达到要求且不需要传送次数，以此类推一个递减序列只需要关注第一位，后面的位置不需要传送次数都可以通过移动完成。所以我们只需要找出所有递减序列的第一位即可，特别的，若位置i是递减序列的第一位，那么c[i-1]对于c[i]也有c[i-1]的贡献，传送次数只需要加上c[i]-c[i-1]即可

代码：

#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"

void solve(){
	int n;
    cin>>n;
    ll c[n+1];
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    ll ans=-1;
    c[0]=0;
    for(int i=1;i<=n;i++){
        if(c[i]<=c[i-1]){
            continue;
        }
        if(c[i]>c[i-1]){
            ans+=c[i]-c[i-1];
        }
    }
    cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

C. Add, Divide and Floor

题意：

给定一个长为n的数组a，每次操作选定一个整数x，并用\(\lfloor \frac{a_i + x}{2} \rfloor\)替换掉所有\(a_i\)，求最少要几次操作可以使所有\(a_i\)相等，若次数小于等于n则输出每次操作x的取值

思路：

将数组a排序，然后每次操作x都选取最小的\(a_1\)

代码：

#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"

void solve(){
	int n;
    cin>>n;
    ll a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    ll ans=0;
    ll k=a[n];
    ll t=a[1];
    while(k>t){
        k=(k+t)/2;
        ans++;
    }
    if(ans>n||ans==0){
        cout<<ans<<endl;
    }else{
        cout<<ans<<endl;
        for(int i=1;i<=ans;i++){
            cout<<t<<" ";
        }
        cout<<endl;
    }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

D. Yet Another Monster Fight

题意：

有n个血量为\(a_i\)的怪物，魔法师可以选定一个怪物放出伤害为x的连锁闪电咒，然后连锁闪电咒会攻击已经收到攻击的怪物的隔壁的怪物，伤害减1，以此类推，每个怪物只能攻击一次，求连锁闪电咒的初始伤害x的最小值

思路：

先预处理两个数组，第一个数组为初始攻击位置k在\(a_i\)右边的情况，\(prermax_i\)表示前i个数最晚被攻击到时要求初始伤害的最小值，（例如\(a_i\)最晚被攻击到时至少需要\(a_i\)的伤害，它右边有n-i个数，最糟糕的情况下初始伤害至少要\(a_i\)+n-i），\(prermax_i\)的转移方程为prermax[i]=max(prermax[i-1],a[i]+n-i)；同理可以得到\(prelmax_i\)。枚举初始攻击怪物的位置k，在初始攻击位置k的条件下最小初始伤害为max(a[k],prermax[k-1],prelmax[k+1])，求所有k的情况下的答案的最小值。

代码：

#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const long long INF = 0x3f3f3f3f3f3f3f3f;
typedef long long ll;
#define endl "\n"

void solve(){
	int n;
    cin>>n;
    ll a[n+1];
    int k=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll prermax[n+1],prelmax[n+2];
    prermax[0]=0;
    for(int i=1;i<=n;i++){
        ll num=a[i]+n-i;
        prermax[i]=max(prermax[i-1],num);
    }
    prelmax[n+1]=0;
    for(int i=n;i>=1;i--){
        ll num=a[i]+i-1;
        prelmax[i]=max(prelmax[i+1],num);
    }
    ll ans=a[k];
    ll ans1=INF;
    for(int k=1;k<=n;k++){
        ans=a[k];
        ans=max(ans,prermax[k-1]);
        ans=max(ans,prelmax[k+1]);
        ans1=min(ans1,ans);
    }
    cout<<ans1<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t=1;
	
//	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}