题解：P12543 [APIO2025] 转杆

hhoppitree · 2025-05-19 12:56:30 · 题解

将直线按照幅角排序后，依次将第 \left\lceil\dfrac{n}{2}\right\rceil+i 条直线转至与第 i 条直线垂直即可（i=1,2,\cdots,\left\lfloor\dfrac{n}{2}\right\rfloor），操作次数 \left\lfloor\dfrac{n}{2}\right\rfloor。

代码实现：

#include <bits/stdc++.h>
#include "rotate.h"

using namespace std;

void energy(int n, vector<int> a) {
    vector< pair<int, int> > p;
    for (int i = 0; i < n; ++i) p.emplace_back(a[i], i);
    sort(p.begin(), p.end());
    for (int i = 0, j = (p.size() + 1) / 2; j < p.size(); ++i, ++j) {
        rotate({p[j].second}, p[i].first + 25000 - p[j].first);
    }
}