ABC429-D - Pop and Insert · znzryb

## 题目大意

有一个周长为 $M$ 的池塘，岸边有一个小屋和 $N$ 个人。定义地点 $x$ 为从小屋顺时针走 $x$ 距离的位置（ $0 \leq x < M$ ）。第 $i$ 个人站在地点 $A_i$ 处，多个人可能站在同一位置。

对于 $i = 0, 1, \ldots, M-1$ ，定义 $X_i$ ：

1. 高橋君从地点 $(i+0.5)$ 出发，开始顺时针移动

1. 他会一直移动，直到遇到的人数总计达到 $C$ 人或更多时停止

1. $X_i$ 是他遇到的总人数（如果停止位置有多人，全部计入，因此 $X_i$ 可能大于 $C$ ）

求所有 $X_i$ 的总和： $\sum_{i=0}^{M-1} X_i$ 

**输入格式：**

- 第一行： $N$ $M$ $C$ 

- 第二行： $A_1$ $A_2$ $\ldots$ $A_N$ 

**输出格式：**

- 一个整数，表示 $X_i$ 的总和

## 思路讲解

## AC代码

[https://atcoder.jp/contests/abc429/submissions/70464977](https://atcoder.jp/contests/abc429/submissions/70464977)



::: 源代码

```cpp
// by Gospel_rock
// title: D - On AtCoder Conference
// timeLimit: 2000
// url: https://atcoder.jp/contests/abc429/tasks/abc429_d
#include <algorithm>
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT, C;

void Solve() {
    cin >> N >> M >> C;
    vector<ll> A(N);
    // map<ll,ll> freq;
    FOR(i, 1, N) {
        cin >> A[i - 1];
        // freq[A[i]]++;
    }
    vector<ll> sa(all(A));
    sort(all(sa));
    sa.resize(unique(all(sa)) - sa.begin());
    ll sz = SZ(sa);
    vector<ll> freq(SZ(sa) + 1);
    auto findi = [&](ll x) {
        ll idx = lower_bound(all(sa), x) - sa.begin();
        return idx;
    };
    auto caldis = [&](ll l, ll r) {
        l %= sz;
        if (l < 0)
            l += sz;
        l = sa[l];

        r %= sz;
        if (r < 0)
            r += sz;
        r = sa[r];

        ll dis = 0;
        if (r > l) {
            dis = r - l;
        } else {
            dis = M + (r - l);
        }
        // if(dis==0) dis=M;
        return dis;
    };
    FOR(i, 1, N) { freq[findi(A[i - 1])]++; }
    // for(auto it1=freq.begin();it1!=freq.end();++it1){
    //     for(auto it2=freq.begin();it2;){

    //     }
    // }

    ll up = 0;
    ll sum = 0;
    ll ans = 0;
    FOR(i, 0, sz - 1) {
        if (up <= i) {
            sum = 0;
            up = i;
        }
        FOR(j, up, 2 * sz) {
            sum += freq[j % sz];
            if (sum >= C) {
                ans += caldis(i - 1, i) * sum;
#ifdef LOCAL
                debug(sum);
                debug(j);
                debug(caldis(i - 1, i));
#endif
                sum -= freq[j % sz];
                sum -= freq[i];
                up = j;

                break;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // cin>>lT;
    // while(lT--)
    Solve();
    return 0;
}
/*
AC
https://atcoder.jp/contests/abc429/submissions/70464977

*/
```


:::


## 心路历程（WA，TLE，MLE……）