BZOJ2600: [IOI2011]ricehub

2015.01.16 07:54 Fri| 4 visits oi_2015| 2015_刷题日常| Text

Solution

受了两天后缀自动机带来的**一样的折磨……QAQ 多么悲惨。

晚上被赶去一楼机房刷水题QAQ wyf大神一天刷十道题,其中还有两道出自 IOI。多么厉害……

结论:在一段左端点编号为 a,右端点编号为 b 的稻田中,若最小化花费需将谷仓建在第 (a+b)/2 块稻田处。

于是简单维护一个单调队列(我这 sx 这么简单的事情为什么还用了 deque...,还懒得用 c-free 测样例,WA 好久……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005

int r, ans;
long long l, b, x[N], sum[N];
deque<int> q;

long long query(int ls, int rs)
{
    int mid = (ls + rs) >> 1;
    return sum[rs] - sum[mid] - x[mid] * (rs - mid) +
           sum[ls - 1] - sum[mid - 1] + x[mid] * (mid - ls);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> r >> l >> b;
    for (int i = 1; i <= r; ++i)
        cin >> x[i], sum[i] = sum[i - 1] + x[i];
    for (int i = 1; i <= r; ++i)
    {
        q.push_back(i);
        while (query(q.front(), i) > b)
            q.pop_front();
        ans = max(ans, int(q.size()));
    }
    cout << ans << endl;
}