题解：P11671 [USACO25JAN] Farmer John's Favorite Operation S

· · 题解

P11671 [USACO25JAN] Farmer John's Favorite Operation S 题解

Preface

这场太难了。前两题做出来之后本来以为进金稳了，结果剩 45 分钟第三题愣是第一个点都没拿到。700 分数线也太高了吧。

这题主要是二分查找和前缀和断环为链两种思路，但是我有第三种 = 差分斜率。

好吧可能是因为我 USACO 最近刷的实在太多了而且还没过，但是真的没人发现和这几乎做法一样吗？

Problem Statement

p11671。

Solution

首先发现因为要取模 x 显然只能在 0 和 m 之间。

因此问题就是求最优的 x 使得 n 个对于 x 的分段函数的和最小。

然后看到要求一个函数最值我直接开始乱搞三分，喜提零分。因为显然不但总函数不是单峰的，单个数的函数都不是，因为一个数既可以加又可以减只要最后余数是零。

此时玩几组数据突然发现似乎每一个函数 i 只有两个断点，当 x 等于 a_i 模 m 时，和当加到余数为零比减到余数为零（或者反过来）更快时。

这时候在画几个函数出来发现真是这样，只不过断点虽然固定，但是函数最后的形状还是要分讨，主要看 m 的奇偶性和 a_i 模 m 相比于 \dfrac{m}2 的大小。

再进一步，发现对于全部 i 个子函数的和组成的 sum 函数，我们其实可以用差分维护它的斜率，因为它最多变化 2 \cdot n 次。因此把每一个断点记作一个 event 放入一个数组，并按 x 从小到大扫，记录当前斜率，用它出（和上个断点的位置及函数值）算当前的函数值。对于全部 2n 个断点上的值求 \min 就是答案。

代码里有很多注释。

Code

/*
differenciating slope??? not sure if it's an actual thing
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n, m, a[200005], ans, sum, slo;
vector< pair<int, pair<int, int> > > event;
//at most 3 each
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        //when, and by how much
        sum = 0;
        slo = 0;
        ans = INT_MAX;
        while(event.size())event.pop_back();
        for(int i = 1; i <= n; i++){
            cin>>a[i];
        }
        for(int i = 1; i <= n; i++){
            int re = a[i] % m;
            int b1 = re;
            int b2;
            if(m % 2 == 0){
                if(re <= (m / 2))b2 = re + (m / 2);
                else b2 = re - (m / 2); 
            }else{
                if(re <= (m / 2))b2 = re + (m / 2);
                else b2 = re - (m / 2 + 1); 
            }
            //b1 and b2 are the two break points
            sum += min(re, m - re);
            //sum = the answer when x == 0 
            if(b1 > b2)slo += 1;
            else slo -= 1;
            //determines the inital slope, upwards or downwards
            if(m % 2 == 1){
                event.push_back({b2, {-1, i}});
                //reach b2, stay
                event.push_back({b2 + 1, {-1, i}});
                //start decreasing              
            }else{
                event.push_back({b2, {-2, i}});
                //start decreasing right away
            }
            event.push_back({b1, {2, i}});
            //reach the remainder itself, start growing again
        }
        sort(event.begin(), event.end());
        int la = 0;
        ans = sum;
        for(int i = 0; i < event.size(); i++){
            int tim = event[i].first;
            int val = event[i].second.first;
            int id = event[i].second.second;
            //tim = time of this event
            //val = how much is changed
            //id = who's changed. not really necessary
            sum += (tim - la) * slo;
            //find current sum
            la = tim;
            ans = min(sum, ans);
            //compare with answer
            slo += val;
            //change slope
        }
        cout<<ans<<endl;
    }
    return 0;
}

After thought

真的和 2018 银组的 Teleportation 好像呀！唉，提刷多了就是这样。建议大家都去看一下那道题。

求赞。