newcoder H肥猪（单调队列 / 线段树）题解

题意：

小B来到了一个异世界，成为了肥猪之王。
在这个异世界，共有n种肥猪，编号分别为1，...，n。
小B希望集齐这n种肥猪。
召集肥猪有两种方式：
1. 花费a[i]的金币召唤一只编号为i的肥猪。
2. 花费x的金币使所有已召集的肥猪进化。
即编号为i的肥猪编号变成i+1，特殊的，编号为n的肥猪编号变成1。

请问小B最少要花多少金币才能集齐n种肥猪。

链接：https://ac.nowcoder.com/acm/contest/332/H
来源：牛客网

思路（官方）：

从0到n-1枚举第二种操作的使用次数step，那么对于最终得到的编号为i的肥猪，假如它是召唤编号为j的肥猪然后进化多次得到的，则一定有 i−step≤j≤ii−step≤j≤i ，并且这是充要的，即它可以由这个区间的任何一个j召唤后进化多次得到。因此只用这个区间的a[j]的最小值就是得到i的代价。把所有i的代价相加再加上step*x就是step对应的最小代价。注意，这个题目是一个环而不是链，这只需要将a复制一份即可。求区间最小值有很多方法，比如单调队列。时间复杂度 O(n2) 。

之前我自己想的是直接找生成每一个点的最小代价（a[k] + step * x），然后保存最大步长，但是这里有个问题，就是我这个step其实是公用的，按照我原来的思路用a[k] + step * x去找最小代价，那么其实是误判了最佳情况，所以wa了orz

单调队列好久没写了...凑活写了一下...

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<string>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int MOD = 1e9 + ;

const ll INF = 1e19;

ll a[maxn << ], q[maxn << ], pos[maxn << ];  //递增队列

ll n, x;

int main(){

    scanf("%lld%lld", &n, &x);

    for(int i = ; i < n; i++){

        scanf("%lld", &a[i]), a[n + i] = a[i];

    }

    ll ans = INF;

    for(int step = ; step <= n - ; step++){

        int head = , tail = ;

        ll ret = ;

        for(int i = n - step; i < n; i++){

            while(head < tail && q[tail - ] >= a[i]) tail--;

            q[tail] = a[i];

            pos[tail++] = i;

        }

        for(int i = n; i < n + n; i++){

            while(head < tail && q[tail - ] >= a[i]) tail--;

            q[tail] = a[i];

            pos[tail++] = i;

            while(head < tail && pos[tail - ] - pos[head] > step) head++;

            ret += q[head];

        }

        ret = ret + step * x;

        ans = min(ans, ret);

    }

    printf("%lld\n", ans);

    return ;

}