CF1614B Divan and a New Project

原题链接

题意

有一条坐标轴上有 $n+1$ （编号为 $0?n$ ） 个建筑，其中他要从第0个建筑去第 $i$ 个建筑 $a_i$ 次 (往返) ，问这些建筑该怎样建造才能使要走的路最少?

输出要走的总距离
和第 i 建筑在哪个坐标上？

思路

使建筑0在 0 点上，别的按要走的次数从小到大排序，分别放在原点两边，以此类推。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
struct name{
    int a; //次数int flag;//位置 
}num[N];bool cmp(name a, name b)
{
    return a.a > b.a;
}signed main()
{
    int t; cin >> t;while (t -- ){
    int n;cin >> n;for (int i = 1; i <= n; i ++ ){
    cin >> num[i].a;num[i].flag = i;}sort(num + 1, num + 1 + n, cmp);int cnt = 1;int ans[N];int sum = 0;for (int i = 1; i <= n; i ++ ){
    sum += (abs(cnt) * num[i].a);ans[num[i].flag] = cnt;if (cnt < 0){
    cnt *= -1;cnt ++;}else{
    cnt *= -1;}}cout << sum * 2 << endl;cout << 0 << " ";for (int i = 1; i <= n; i ++ ) cout << ans[i] << " ";cout << endl;}return 0;
}

总结

这个比赛时就写过了