Codeforces Round #757 (Div. 2) B. Divan and a New Project
题目标签：B题
The company 'Divan's Sofas' has announced plans to construct n+1 distinct buildings on a coordinate line, subject to the condition that...
- Every building has an integer value as its coordinate;
- Any pair of buildings do not occupy the same spatial position.
Denote x_{xi} as the coordinate of the ith building. It takes Divan |xi−xj| minutes to travel from building i to building j, where |y| represents the absolute value of y.
All buildings that Divan plans to construct can be assigned numbers ranging from 0 to nn. The executive will reside in building number 0, which serves as the new headquarters for "Divan's Sofas." Within the initial ten years post-construction, Divan will make visits to the ii-th building on aiai occasions, each occasion requiring an expenditure of 2⋅|x₀−x_i| minutes walking time.
Divan requests that you determine the coordinates for a total of n+1 buildings in order that over the next ten years the businessman will spend the least amount of time walking.
Input
Each test comprises multiple test cases. The initial line includes an integer value t (1≤t≤103), which indicates the total number of test cases.
The initial line of each case includes a whole number n, where 1 ≤ n ≤ 2⋅105 — representing the count of buildings that "Divan's Sofas" plans to construct, excluding the headquarters building.
The second line consists of an ordered series a_1, \dots, a_n, where each a_i represents the number of visits made to the i-th building.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅105.
Output
In each test case, be sure to output T — representing the minimal time Divan needs to walk.
On the second line output a sequence consisting of n+1 integers x₀, x₁, ..., xₙ where each xi (−¹⁰⁶ ≤ xi ≤ ¹⁰⁶) represents the selected coordinate value of the ii-th building. It is possible to demonstrate that all coordinates are within ¹⁰⁶.
If there are multiple answers, print any of them.
Example
input
output
Note
Let's look at the first example.
Divan is scheduled to visit each of the first building (a₁) once, the second building (a₂) twice, and each of the third buildings (a₃) three times. An optimal solution would include visiting these buildings accordingly.
- the headquarters is located in x0=2;
- x1=4: Divan will spend 2⋅|x0−x1|⋅a1=2⋅|2−4|⋅1=4 minutes walking to the first building;
- x2=1: Divan will spend 2⋅|x0−x2|⋅a2=2⋅|2−1|⋅2=4 minutes walking to the second building;
- x3=3: Divan will spend 2⋅|x0−x3|⋅a3=2⋅|2−3|⋅3=6 minutes walking to the third building.
Summing up, Divan will allocate a total of 4 + 4 + 6 = 14 minutes. It can be demonstrated that it is impossible to arrange the buildings in a way that allows the businessman to spend less time.
Among others, x=[1,3,2,0], x=[−5,−3,−6,−4] are also correct answers for the first example.
问题描述：假设共有n+1座建筑排列在同一直线上且每座建筑的位置互不相同。两座建筑之间的往返时间为2乘以它们的位置差的绝对值，并给定每座建筑被访问的次数要求计算所需总时间和各座建筑的位置分布情况（注：所有位置值必须满足-1e6 ≤ 位置 ≤ 1e6）
思路：首先按照访问频率由高到低进行排序。由于仅有200,000栋建筑，在此前提下我们将位于该房子的位置设定为1e5 + 5（即第100,001个位置），随后根据奇偶性向前或向后依次放置即可完成布局安排。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
ll a;
ll i;
ll num;
}arr[200005];
bool cmp(node a, node b){
return a.a > b.a;
}
bool cmp1(node a, node b){
return a.i < b.i;
}
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
int n;
while(t--){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> arr[i].a;
arr[i].i = i;
}
arr[0].num = 100005;
arr[0].i = 0;
sort(arr + 1, arr + n + 1, cmp);
for(int i = 1; i <= n; i++){
if(i & 1){
arr[i].num = arr[0].num + (i + 1) / 2;
}else{
arr[i].num = arr[0].num - (i / 2);
}
}
ll sum = 0;
sort(arr + 1, arr + 1 + n, cmp1);
for(int i = 1; i <= n; i++){
sum += 2ll * arr[i].a * abs(arr[i].num - arr[0].num);
}
cout << sum << "\n";
for(int i = 0; i <= n; i++){
if(i != 0){
cout << " ";
}
cout << arr[i].num;
}
cout << "\n";
}
return 0;
}