Codeforces #731 (div3) E. Air Conditioners

E. Air Conditioners

链接：****E. Air Conditioners
On a strip of land of length n there are k air conditioners: the i-th air conditioner is placed in cell ai (1≤ai≤n). Two or more air conditioners cannot be placed in the same cell (i.e. all ai are distinct).

Each air conditioner is characterized by one parameter: temperature. The i-th air conditioner is set to the temperature ti.

Example of strip of length n=6, where k=2, a=[2,5] and t=[14,16].
For each cell i (1≤i≤n) find it's temperature, that can be calculated by the formula
min1≤j≤k(tj+|aj?i|),
where |aj?i| denotes absolute value of the difference aj?i.

In other words, the temperature in cell i is equal to the minimum among the temperatures of air conditioners, increased by the distance from it to the cell i.

Let's look at an example. Consider that n=6,k=2, the first air conditioner is placed in cell a1=2 and is set to the temperature t1=14 and the second air conditioner is placed in cell a2=5 and is set to the temperature t2=16. In that case temperatures in cells are:

temperature in cell 1 is: min(14+|2?1|,16+|5?1|)=min(14+1,16+4)=min(15,20)=15;
temperature in cell 2 is: min(14+|2?2|,16+|5?2|)=min(14+0,16+3)=min(14,19)=14;
temperature in cell 3 is: min(14+|2?3|,16+|5?3|)=min(14+1,16+2)=min(15,18)=15;
temperature in cell 4 is: min(14+|2?4|,16+|5?4|)=min(14+2,16+1)=min(16,17)=16;
temperature in cell 5 is: min(14+|2?5|,16+|5?5|)=min(14+3,16+0)=min(17,16)=16;
temperature in cell 6 is: min(14+|2?6|,16+|5?6|)=min(14+4,16+1)=min(18,17)=17.
For each cell from 1 to n find the temperature in it.

Input

The first line contains one integer q (1≤q≤104) — the number of test cases in the input. Then test cases follow. Before each test case, there is an empty line.

Each test case contains three lines. The first line contains two integers n (1≤n≤3?105) and k (1≤k≤n) — the length of the strip of land and the number of air conditioners respectively.

The second line contains k integers a1,a2,…,ak (1≤ai≤n) — positions of air conditioners on the strip of land.

The third line contains k integers t1,t2,…,tk (1≤ti≤109) — temperatures of air conditioners.

It is guaranteed that the sum of n over all test cases does not exceed 3?105.

Output

For each test case output n integers separated by space: temperatures of air in cells.

朴素做法时间复杂度很高，计算出对每个格子每个冰箱的影响，在进行比较；

正解：每个冰箱对每个格子的影响是有规律的，距离每增加一格，温度升高一度，

所以多台冰箱对格子的影响规律：可以从向左向右两个方向来说，例如从向右来说：

若第一台冰箱对第二台冰箱的影响的温度大于第二台冰箱温度，则之后再向右的温度都取决于第二台冰箱

之后以此类推。

思路：从左从右两个方向各自进行一次遍历，对每个各格子取较小值；

#include 
using namespace std;
const int N = 3e5+100;

int n, k;
paira[N];
int l[N], r[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T; cin >> T;
    while(T--)
    {
        cin >> n >> k;
        for(int i = 1; i <= k; i++) cin >> a[i].first;
        for(int i = 1; i <= k; i++) cin >> a[i].second;
        sort(a+1, a+1+k);//sort注意所给数据不是按位置的，先进行排序
        //From left
        int t = a[1].second + a[1].first;
        for(int i = 1, j = 1; i <= n; i++)
        {
            t++;
            if(i == a[j].first)
            {
                t = min(a[j].second, t);
                if(j < k) j++;
            }
            l[i] = t;
        }
        //From right
        t = a[k].second + n - a[k].first + 1;
        for(int i = n, j = k; i >= 1; i--)
        {
            t++;
            if(i == a[j].first)
            {
                t = min(a[j].second, t);
                if(j > 1) j--;
            }
            r[i] = t;
        }
        for(int i = 1; i <= n; i++)
            cout << min(l[i], r[i]) << " ";
        cout << endl;
    }
    return 0;
}