CodeForces 1393C Pinkie Pie Eats Patty-cakes

$Pinkie$ $Pie$ $Eats$ $Patty-cakes$

思路：
自我感觉这题比B简单，它的目的是让连续不同的最小值最大，呢么我们就利用出现最多的当作隔板，看能把这个序列最大分成几段，显然这个中间段就算最大的，不然挤在一起，连续最小的段肯定存在比将序列分成最大几段的要小。

参考代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
//#define ll long long
const ll N = 1e3 + 5;
const ll maxn = 1e5 + 20;
const ll mod = 1000000007;
int inv[maxn], vis[maxn], dis[maxn];
int fac[maxn], a[maxn], q[maxn], b[N], c[N];
vector<ll> vec;
//typedef pair<ll, ll> p;
//priority_queue<p, vector<p>, greater<p> > m;
// ll sum[maxn], a[maxn];
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
map<ll, ll> mp;
ll ksm(ll a, ll b)
{
    a %= mod;
    ll ans = 1ll;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1ll;
    }
    return ans;
}
// ll dp[105][16005];
// string p = "abacaba";
// queue<ll> qk, q;
//vector<ll> vec;
// ll sumx[maxn], sumy[maxn], sumk[maxn];
int cnt;
map<int, int> p;
struct node
{
    int ls, rs, sum;
} tr[maxn * 32];
void inser(int &k, int L, int R, int pos, int w)
{
    if (!k)
        k = ++cnt;
    tr[k].sum += w;
    if (L == R)
        return;
    int mid = L + R >> 1;
    if (mid >= pos)
        inser(tr[k].ls, L, mid, pos, w);
    else
        inser(tr[k].rs, mid + 1, R, pos, w);
}
int query(int k, int L, int R, int ik)
{
    if (L == R)
        return L;
    int sk = tr[tr[k].ls].sum;
    int mid = L + R >> 1;
    if (sk >= ik)
        return query(tr[k].ls, L, mid, ik);
    else
        return query(tr[k].rs, mid + 1, R, ik - sk);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t, n, ans;
    // scanf("%lld", &t);
    cin >> t;
    while (t--)
    {
        p.clear();
        int n, ans = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i], ans = max(++p[a[i]], ans);
        int k = 0;
        for (int i = 0; i < n; i++)
            if (p[a[i]] == ans)
                k++, p[a[i]] = 0;
        //cout << ans << ' ' << k << endl;
        int res = (n - k * ans) / (ans - 1) + k - 1;
        cout << res << endl;
    }
}

本文地址：https://blog.csdn.net/yangzijiangac/article/details/107879329