HDU - 6444（单调队列+思维）

链接：HDU - 6444

题意：给出一个包含 n 个数的环，每个数都有一个价值，起点任选，每次跳顺时针跳 k 个数，在哪个数就能获得该价值（包括起点），最多取 m 次，问最少需要补充多少价值，所拿的价值和才能大于等于 s 。

题解：从不同起点出发会获得很多不同的环，将每个环取出来讨论。

1.环的总价值和小于等于0，那么表示跑再多圈也没用，求一段长度不大于 min(m, 圈长) 的最大区间和即可。

2.环的总价值和大于0，那么多跑一圈价值就大一点，就尽量多跑几圈就可以了，但是最后一个满圈是个坑点，最优解可能不跑完最后一个满圈，需要注意。

#include <bits/stdc++.h>

using namespace std;

const double EPS = 1e-;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

const int maxn = 1e5 + ;

long long n, s, k;

int m;

long long sum[maxn], a[maxn], num[maxn];

vector<long long> v[maxn];

set<int> st;

list<long long> Q;

long long Cal(long long a[], int n, int k)

{

    for(int i = ; i <= n; i++) sum[i] = sum[i - ] + a[i - ];

    Q.clear(); Q.push_back();

    long long ans = ;

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

        while(!Q.empty() && sum[Q.back()] > sum[i]) Q.pop_back();

        Q.push_back(i);

        while(!Q.empty() && i - Q.front() > k) Q.pop_front();

        int j = Q.front();

        ans = max(ans, sum[i] - sum[j]);

    }

    return ans;

}

int main()

{

    int T, cas = ;

    scanf("%d", &T);

    while(T--){

        scanf("%lld%lld%d%lld", &n, &s, &m, &k);

        st.clear();

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

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

            st.emplace(i);

        }

        int cnt = ;

        while(!st.empty()){

            num[cnt] = ;

            v[cnt].clear();

            int x = *st.begin();

            while(st.count(x)){

                st.erase(x);

                v[cnt].push_back(a[x]);

                num[cnt] += a[x];

                x = (x + k) % n;

            }

            cnt++;

        }

        long long ans = ;

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

            int N = v[i].size();

            for(int j = ; j < N; j++) a[j] = a[j + N] = v[i][j];

            if(num[i] <= ){

                ans = max(ans, Cal(a, N << , min(N, m)));

            }

            else{

                int d = m / N;

                int r = m % N;

                if(d > ){

                    long long mx1 = Cal(a, N << , N);

                    long long mx2 = Cal(a, N << , r);

                    if(mx1 > mx2 + num[i]) ans = max(ans, (d - ) * num[i] + mx1);

                    else ans =  max(ans, d * num[i] + mx2);

                }

                else ans = max(ans, Cal(a, N << , r));

            }

        }

        if(ans >= s) ans = ;

        else ans = s - ans;

        printf("Case #%d: %lld\n", cas++, ans);

    }

    return ;

}