Road Widening

题意翻译

## 题目描述 $S$ 市市长讨厌树木和草坪。他们占用了如此多的空间，而且他们占用的地方可能有一条路！市长认为，若拆除没有人需要的草坪，城市的一条街道可能会大大拓宽。此外，这可能有助于减少街上发生的交通堵塞。街道从左至右分为 $ n $ 个部分，每个部分由两个整数表示：道路宽度 $ s_i $ 与 草坪 $ g_i $ 的宽度。 市长需要拆除一部分草坪来拓宽道路。对于长度为 $ g_i $ 的草坪，你可以将它拆除 $ x_i $ ( $ x_i $ $ \le $ $ g_i $ ).同时，道路的宽度 $ s_i $ 加上 $ x_i $。 一方面，市长希望拆除尽可能多的草坪（并用道路代替）。另一方面，他不想造成道路快速加宽或变窄，从而导致车祸。为了避免这种情况，市长决定连续路段的道路宽度最多相差1。 你需要找到市长应拆除的草坪长度，并输出拆除这个长度后，每条道路的宽度。 ## 输入格式 第一行输入一个正整数 $ n $ 表示街道的部分数。 接下来 $ n $ 行，每行输入两个正整数： $ s_i $ 和 $ g_i $ 。 ## 输出格式 第一行输出要拆除的草坪长度。 第二行输出 $ n $ 。 如果没有解决方案，请在第一行输出 -1。 ## 数据范围 $ 1<=n<=2·10^{5} $ $ 1<=s_{i}<=10^{6} $ $ 0<=g_{i}<=10^{6} $ ## 样例 #1 ### 样例输入 #1 ``` 3 4 5 4 5 4 10 ``` ### 样例输出 #1 ``` 16 9 9 10 ``` ## 样例 #2 ### 样例输入 #2 ``` 4 1 100 100 1 1 100 100 1 ``` ### 样例输出 #2 ``` 202 101 101 101 101 ``` ## 样例 #3 ### 样例输入 #3 ``` 3 1 1 100 100 1 1 ``` ### 样例输出 #3 ``` -1 ```

题目描述

Mayor of city S just hates trees and lawns. They take so much space and there could be a road on the place they occupy! The Mayor thinks that one of the main city streets could be considerably widened on account of lawn nobody needs anyway. Moreover, that might help reduce the car jams which happen from time to time on the street. The street is split into $ n $ equal length parts from left to right, the $ i $ -th part is characterized by two integers: width of road $ s_{i} $ and width of lawn $ g_{i} $ . For each of $ n $ parts the Mayor should decide the size of lawn to demolish. For the $ i $ -th part he can reduce lawn width by integer $ x_{i} $ ( $ 0<=x_{i}<=g_{i} $ ). After it new road width of the $ i $ -th part will be equal to $ s'_{i}=s_{i}+x_{i} $ and new lawn width will be equal to $ g'_{i}=g_{i}-x_{i} $ . On the one hand, the Mayor wants to demolish as much lawn as possible (and replace it with road). On the other hand, he does not want to create a rapid widening or narrowing of the road, which would lead to car accidents. To avoid that, the Mayor decided that width of the road for consecutive parts should differ by at most $ 1 $ , i.e. for each $ i $ ( $ 1<=i&lt;n $ ) the inequation $ |s'_{i+1}-s'_{i}|<=1 $ should hold. Initially this condition might not be true. You need to find the the total width of lawns the Mayor will destroy according to his plan.

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<=2·10^{5} $ ) — number of parts of the street. Each of the following $ n $ lines contains two integers $ s_{i},g_{i} $ ( $ 1<=s_{i}<=10^{6} $ , $ 0<=g_{i}<=10^{6} $ ) — current width of road and width of the lawn on the $ i $ -th part of the street.

输出格式

In the first line print the total width of lawns which will be removed. In the second line print $ n $ integers $ s'_{1},s'_{2},...,s'_{n} $ ( $ s_{i}<=s'_{i}<=s_{i}+g_{i} $ ) — new widths of the road starting from the first part and to the last. If there is no solution, print the only integer -1 in the first line.

输入输出样例

输入样例 #1

3
4 5
4 5
4 10

输出样例 #1

16
9 9 10 

输入样例 #2

4
1 100
100 1
1 100
100 1

输出样例 #2

202
101 101 101 101 

输入样例 #3

3
1 1
100 100
1 1

输出样例 #3

-1

题意翻译

## 题目描述 $S$ 市市长讨厌树木和草坪。他们占用了如此多的空间，而且他们占用的地方可能有一条路！市长认为，若拆除没有人需要的草坪，城市的一条街道可能会大大拓宽。此外，这可能有助于减少街上发生的交通堵塞。街道从左至右分为 $ n $ 个部分，每个部分由两个整数表示：道路宽度 $ s_i $ 与 草坪 $ g_i $ 的宽度。 市长需要拆除一部分草坪来拓宽道路。对于长度为 $ g_i $ 的草坪，你可以将它拆除 $ x_i $ ( $ x_i $ $ \le $ $ g_i $ ).同时，道路的宽度 $ s_i $ 加上 $ x_i $。 一方面，市长希望拆除尽可能多的草坪（并用道路代替）。另一方面，他不想造成道路快速加宽或变窄，从而导致车祸。为了避免这种情况，市长决定连续路段的道路宽度最多相差1。 你需要找到市长应拆除的草坪长度，并输出拆除这个长度后，每条道路的宽度。 ## 输入格式 第一行输入一个正整数 $ n $ 表示街道的部分数。 接下来 $ n $ 行，每行输入两个正整数： $ s_i $ 和 $ g_i $ 。 ## 输出格式 第一行输出要拆除的草坪长度。 第二行输出 $ n $ 。 如果没有解决方案，请在第一行输出 -1。 ## 数据范围 $ 1<=n<=2·10^{5} $ $ 1<=s_{i}<=10^{6} $ $ 0<=g_{i}<=10^{6} $ ## 样例 #1 ### 样例输入 #1 ``` 3 4 5 4 5 4 10 ``` ### 样例输出 #1 ``` 16 9 9 10 ``` ## 样例 #2 ### 样例输入 #2 ``` 4 1 100 100 1 1 100 100 1 ``` ### 样例输出 #2 ``` 202 101 101 101 101 ``` ## 样例 #3 ### 样例输入 #3 ``` 3 1 1 100 100 1 1 ``` ### 样例输出 #3 ``` -1 ```