题解：P12543 [APIO2025] 转杆

· · 题解

不同于 std 的做法。

首先可以盯出一个结论：

证明简单，调整法即可。

钦定 v_i=0 为 \text{x} 轴，v_i=25000 为 \text{y} 轴，考虑如何做出最终形态。

我们将所有线分为以下几种：

记红线、黑线、蓝线、绿线的数量分别为 rd,bl,bu,gr。

请注意，一开始需要钦定没有红线和黑线，对于 v_i 为 0 或 25000 的线，将它们钦定为蓝线或绿线。

称将一条蓝线或绿线转为黑线或红线的操作为校正。

在一开始没有红线和黑线的情况下，我们可以交替进行校正操作。

具体地，当 bl \le rd 时，可以将一条蓝线或绿线转为黑线；当 bl \ge rd 时，可以将一条蓝线或绿线转为红线，取等时的选择后面会用到。

在保证夹角和不降的情况下，最后一定有 \big \lfloor \cfrac{n}{2} \big \rfloor 根红线和 \big \lceil \cfrac{n}{2} \big \rceil 根黑线。

考虑怎么保证夹角和不降。

红线校正与黑线校正同理，这里只讨论黑线校正。

不失一般性地，我们钦定 bu \ge gr，否则可以将整个图镜面翻转。

将斜率最大的蓝线转 \theta 的角度校正为黑线。

最劣情况下，这样做对总夹角和的贡献为 \theta(bu-1+rd-bl-gr)。

这样做是对的当且仅当 bu-1+rd-bl-gr \ge 0，所以可以拿到 11 分。

由于此时为黑线校正，bl \le rd，又有 bu \ge gr。

不难得出仅在 bu=gr,bl=rd 时有可能出现错误。

考虑这个局面怎么做。

不难发现这个局面有非常好的性质：

原因是红线黑线数量相同，且一条线与红线黑线的夹角和总为 90^{\circ}。

因此只需考虑蓝绿线之间的夹角和变化。

可以同时转所有的蓝线和绿线，并进行一次校正，但这样花费太高了，只能拿到 74 分。

刚才的做法启发我们转同样数量的蓝线和绿线。

具体地，我们可以同时转动斜率最大的蓝线和绿线各一根，角度为 \theta。

最劣情况下，对夹角和的贡献为 \theta(bu-1-gr+1)+\theta(gr-1-bu+1)=0。

但上述式子有前提条件，即绿线不能变为蓝线，蓝线不能变为绿线。

这是好处理的，令斜率最大的蓝线与 \text{y} 轴夹角为 \theta_1，斜率最大的绿线与 \text{x} 轴夹角为 \theta_2，取 \theta=\min \{ \theta_1 , \theta_2 \} 即可。

由于此时黑线和红线数量相等，所以红线校正和黑线校正都是可行的。

每次花 1 或 2 的代价校正一条线，操作数不超过 2n。

根据上述分析模拟即可。

Code:

#include<bits/stdc++.h>
using namespace std;
void energy(int n,vector<int> v);
void rotate(vector<int> t,int x);
multiset<pair<int,int> > g,b;
void rotate_(int pos,int x)
{
    vector<int> t;
    t.emplace_back(pos);
    rotate(t,(x+50000)%50000);
}
void energy(int n,vector<int> v)
{
    int rd=0,bl=0,bu=0,gr=0;
    for(int i=0;i<n;i++)
    {
        int x=v[i];
        if(x<25000) bu++,b.emplace(x,i);
        else gr++,g.emplace(x,i);
    }
    for(;bu|gr;)
        if(bl<=rd)
        {
            if(bu==gr&&bl==rd)
            {
                vector<int> t;
                int x=(--b.end())->first,y=(--b.end())->second;
                int x_=(--g.end())->first,y_=(--g.end())->second;
                if(50000-x_<25000-x)
                {
                    int del=50000-x_;
                    t.emplace_back(y);t.emplace_back(y_);
                    rd++;
                    rotate(t,del);
                    g.erase(--g.end());gr--;
                    b.erase(--b.end());
                    v[y]=(v[y]+del)%50000;
                    if(v[y]==25000) bl++,bu--;
                    else b.emplace(v[y],y);
                }
                else
                {
                    int del=25000-x;
                    t.emplace_back(y);t.emplace_back(y_);
                    bl++;
                    rotate(t,del);
                    b.erase(--b.end());bu--;
                    g.erase(--g.end());
                    v[y_]=(v[y_]+del)%50000;
                    if(v[y_]==0) rd++,gr--;
                    else g.emplace(v[y_],y_);
                }
            }
            else if(bu>=gr)
            {
                int x=(--b.end())->first,y=(--b.end())->second;
                b.erase(--b.end());
                bu--;bl++;
                rotate_(y,25000-x);
            }
            else
            {
                int x=(g.begin())->first,y=(g.begin())->second;
                g.erase(g.begin());
                gr--;bl++;
                rotate_(y,25000-x);
            }
        }
        else
        {
            if(bu>=gr)
            {
                int x=(b.begin())->first,y=(b.begin())->second;
                b.erase(b.begin());
                bu--;rd++;
                rotate_(y,-x);
            }
            else
            {
                int x=(--g.end())->first,y=(--g.end())->second;
                g.erase(--g.end());
                gr--;rd++;
                rotate_(y,50000-x);
            }
        }
}