30分求助
查看原帖
30分求助
587702
CH3CHO楼主2022/8/15 14:08

只过了第一、二以及最后一个点 qaq。 希望能帮忙看一下问题出在哪里

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
const double pd = 0.00000001;
typedef long long ll;

int n, m, k, t;
ll res = 0;
int minn = INF;
int a[N];
vector<int>ans;

struct Node
{
    int l, r;
    ll sum;
    int min;
}q[N * 4];

void pushup(int u)
{
    q[u].sum = q[u << 1].sum + q[u << 1 | 1].sum;
    q[u].min = min(q[u << 1].min, q[u << 1 | 1].min);
}

void build(int u, int l, int r)
{
    if(l == r) q[u] = {l, r, a[l], a[l]};
    else
    {
        q[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void geta(int u, int l, int r)
{
    if(q[u].l >= l && q[u].r <= r)
    {
        minn = min(q[u].min, minn);
        res += q[u].sum;
    }
    else
    {
        int mid = q[u].l + q[u].r >> 1;
        if(l <= mid) geta(u << 1, l, r);
        if(r > mid) geta(u << 1 | 1, l, r);
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    build(1, 1, n);
    int rev = 0;

    for(int k = 1; k <= n - 2; k ++)
    {
        res = 0, minn = INF;
        geta(1, 1 + k, n);
        double tem = (res - minn) * 1.0 / (n - k - 1);

        if( tem == rev)
            ans.push_back(k);
        else if(tem > rev)
        {
            ans.clear();
            ans.push_back(k);
            rev = tem;
        }
    }

    for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << "\n";
    puts("");

    return 0;
}

2022/8/15 14:08
加载中...