E. Air Conditioners

题目描述：

n个点，k个空调，每个空调有一个温度t_i，每个空调在任意一个点 j 产生的温度是$min{(t_i + |pos[i]-j|)}$，温度不叠加

问每个点的最低温度是多少

思路1：

官方思路是两个dp，从前往后一个，从后往前一个

第一个是 l[i], 表示只考虑在 i 点左边的空调在 i 能产生的最低温度

int p = inf;
for(int i = 1; i <= n; ++i){
p = min(p + 1, val[i]);
l[i] = p;
}

i 点有空调时val[i]为空调温度，否则是inf

同样的，第二个是 r[i], 表示只考虑在 i 点右边的空调在 i 能产生的最低温度

int p = inf;
for(int i = n; i >= 1; --i){
p = min(p + 1, val[i]);
r[i] = p;
}

$ans[i] = min(l[i], r[i])$

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int l[MAX], r[MAX];
int tr[MAX], val[MAX];

void work(){
    cin>>n>>k;
    mem(l, inf);
    mem(r, inf);
    mem(val, inf);
    for(int i = 1; i <= k; ++i){
        cin>>tr[i];
    }
    for(int i = 1; i <= k; ++i){
        cin>>x;
        val[tr[i]] = x;
    }
    int p = inf;
    for(int i = 1; i <= n; ++i){
        p = min(p + 1, val[i]);
        l[i] = p;
    }
    p = inf;
    for(int i = n; i >= 1; --i){
        p = min(p + 1, val[i]);
        r[i] = p;
    }
    for(int i = 1; i <= n; ++i){
        cout<<min(l[i], r[i])<<' ';
    }
    cout<<endl;
}

int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

思路2:

我自己的思路就是写一个类似于堆优化的迪杰斯特拉的bfs，先将有空调的点塞进去，然后更新他旁边的两个点，每次都取当前堆里面价值最低的来更新

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int pos[MAX];
int t[MAX];

priority_queue<pii, vector<pii>, greater<pii> >q;
int ans[MAX];
void bfs(){
    while (!q.empty()) {
        int u = q.top().second;
        int val = q.top().first;
        q.pop();
        if(ans[u])continue;
//        cout<<u<<' '<<val<<endl;
        ans[u] = val;
        if(u - 1 > 0){
            q.push(m_p(val + 1, u - 1));
        }
        if(u + 1 <= n){
            q.push(m_p(val + 1, u + 1));
        }
    }
    for(int i = 1; i <= n; ++i){
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}

void work(){
    cin>>n>>k;
    mem(ans, 0);
    for(int i = 1; i <= k; ++i)cin>>pos[i];
    for(int i = 1; i <= k; ++i){
        cin>>x;
        q.push(m_p(x, pos[i]));
    }
//    while (!q.empty()) {
//
//        cout<<q.top().second<<' '<<q.top().first<<endl;
//    }
    bfs();
}

int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}