CF1547E Air Conditioners

题目传送门

这道题我的思路严重劣于题解思路，所以请慎用

但是自认为我的贪心比dp好理解点

题意

有 \(q\) 组数据，每组第一排表示有 \(n\) 个方格和 \(k\) 个空调，第二排是每个空调的位置 \(a_i\) ,第三排是每个空调的温度 \(t_i\) 。

每个空调对周围的影响是递减的，所以一个空调周围的温度是公差为 \(1\) 的递增等差数列。如果一个方格同时被多个空调影响，那么取最小值。空调所在的方格温度就是空调的温度。

输出所有方格的温度。

思路

假如现在有\(j_1=i-1\)并且已知位置\(j\)的最低温为\(k\)，那么：

• 如果\(i\)的位置上有空调，那么他的最低温就是\(min(f_i,k)\)

• 否则，就是\(k±1\)

但很明显不止于此，\(j_2=i+1\)也是一种情况：（\(k\)的意义同上）

• 如果\(i\)的位置上有空调，那么他的最低温就是\(min(f_i,k)\)

• 否则，就是\(k±1\)

（其中\(f_i\)表示第个位置的空调的最低温，而\(±\)的确切数值应该看影响当前位置的空调的位置）

所以，从前往后可从后往前分别处理一次并存下来，最后输出最大值即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn=3e5+10;
ll f[Maxn],a[Maxn];
ll n,k,cnt,t;
ll fr[Maxn],bk[Maxn];
void run()
{
    cin>>n>>k;fr[1]=bk[n]=1e10;cnt=0;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=k;i++) cin>>a[i];
    for(int i=1;i<=k;i++) cin>>f[a[i]];

    for(int i=1;i<=k;i++)
    {
        if(f[a[i]]+(a[i]-1)<=fr[1])
        {
            fr[1]=f[a[i]]+(a[i]-1);
            cnt=a[i];
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(i>cnt) t=1;
        else if(i<cnt) t=-1;
        else t=0;
        if(f[i]!=-1 && fr[i-1]+t>f[i]) fr[i]=f[i],cnt=i;
        else fr[i]=fr[i-1]+t;
    }
    for(int i=1;i<=k;i++)
    {
        if(f[a[i]]+(n-a[i])<=bk[n])
        {
            bk[n]=f[a[i]]+(n-a[i]);
            cnt=a[i];
        }
    }
    for(int i=n-1;i>=1;i--)
    {
        if(i>cnt) t=1;
        else if(i<cnt) t=-1;
        else t=0;
        if(f[i]!=-1 && bk[i+1]-t>f[i]) bk[i]=f[i],cnt=i;
        else bk[i]=bk[i+1]-t;
    }
    for(int i=1;i<=n;i++) cout<<min(fr[i],bk[i])<<" ";
    cout<<endl;
    // for(int i=1;i<=n;i++) cout<<fr[i]<<" ";
    // cout<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) run();
    system("echo. & pause");
    return 0;
}