CF1547E Air Conditioners

I read several solutions to this problem , I also feel that I have learned some knowledge

The question

Let's start with the meaning of the title

The length is n In a one-dimensional space line , Given k An air conditioner , At the same time, its position and set temperature are given . Ask the temperature of each cell .

Temperature calculation formula ：
$$\underset{1\le j\le k}{\min }(t_j+|a_j-i|),$$
The minimum value of the set temperature of all air conditioners plus the distance to this point is the temperature of this point

practice

First of all, I think the first method is the most applicable , At the same time, it can also correspond to the multi-source that I simply learned some time ago BFS

Take each air conditioner as a starting point , Join the queue at the same time , Update the adjacent points with the currently known points . The answer to each point can actually be based on the temperature on the left and right sides , To get , Through the formula, we know , You can add the increased distance to the minimum value of the left and right points 1 Compare with the current answer to this point and take the smallest

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define re return
#define pb push_back
#define Endl "\n"
#define endl "\n"
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 3e5 + 10;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int dx[4] = {
    -1,0,1,0};
int dy[4] = {
    0,1,0,-1};

int T;
int n, k;
int a[N];
int t[N];
int dis[N];

int main(){
    
    cin >> T;
    while(T--){
    
        memset(dis, 0x3f, sizeof(dis));
        priority_queue<PII, vector<PII>, greater<PII>> q;

        cin >> n >> k;

        for (int i = 1; i <= k; i++){
    
            cin >> a[i];
        }

        for (int i = 1; i <= k; i++){
    
            cin >> t[i];
            q.push({
    a[i], t[i]});
        }

        while(!q.empty()){
    
            auto t = q.top();
            q.pop();
            if(t.y < dis[t.x]){
    
                dis[t.x] = t.y;
                if(t.x + 1 <= n)
                    q.push({
    t.x + 1, t.y + 1});
                if(t.x - 1 >= 1)
                    q.push({
    t.x - 1, t.y + 1});
            }
        }

        for (int i = 1; i <= n; i++){
    
            cout << dis[i] << " ";
        }
        cout << Endl;
    }
}

Source of ideas ：Messywind

https://blog.csdn.net/messywind/article/details/118653468?spm=1001.2014.3001.5501

According to the bold words above , We can actually know , The answer of each point is only updated by the answers determined at the left and right ends , Or left +1 influence , Or by the right +1 influence , This constitutes a linear DP problem

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define re return
#define pb push_back
#define Endl "\n"
#define endl "\n"
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 3e5 + 10;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int dx[4] = {
    -1,0,1,0};
int dy[4] = {
    0,1,0,-1};

int T;
int n, k;
int a[N];
int t[N];

int main(){
    
    cin >> T;
    while(T--){
    
        memset(t, 0x3f, sizeof(t));

        cin >> n >> k;

        for (int i = 1; i <= k; i++){
    
            scanf("%d", &a[i]);
        }

        for (int i = 1; i <= k; i++){
    
            int x;
            cin >> x;
            t[a[i]] = x;
        }

        for (int i = 1; i <= n; i++)
            t[i] = min(t[i - 1] + 1, t[i]);

        for (int i = n; i >= 1; i--)
            t[i] = min(t[i + 1] + 1, t[i]);

        for (int i = 1; i <= n; i++)
            cout << t[i] << " ";
        cout << Endl;
    }
}

Source of ideas ：https://blog.csdn.net/weixin_50909982/article/details/118895522