HDU 6444 Neko's loop（单调队列）

Neko has a loop of size

n

InputThe first line contains only one integer $T (T \leq 50)$ OutputFor each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the answer.Sample Input

Sample Output

Case #1: 0
Case #2: 2


题意：
给n个数字，当位于某一个数字时，可以得到这个数字的快乐值（可以重复获得），可以走m步，每次向后跳k格（循环），问快乐值要达到s，那么初始快乐值的最小值是多少？
思路：
这是2018ccpc的网络赛的题，暑假看着学长打比赛，在傍边连读题都帮不上。。。。

首先有一个显而易见的结论，对于某一个起点，跳着跳着就会回到起点，也就是说，一定存在循环节。
其次显而易见的，就是对于某一个数，只会存在于一个循环节中。
那么如果不考虑循环节的起点差异，找出所有循环节就是O(n)的。而实际上我们确实不用考虑，原因接下来再说。

我们可以轻易的算出某个循环节中所有元素的和--sum，因为存在负数，所以sum可能是负数。
再声明一下，len是循环节长度。
若sum<0，那么最多只需走min（m,len）步就可以得到最优解。
若sum>0,则需要先走m/len-1圈，为什么减一，其他博客有详解（博主太懒了），然后最多走m-(m/len-1)*len)步


先说这后面多出来的步数，假设是p步，这p步在sum<0时，p<=len，sum<0时,len<=p<=2*len。
为了求出这p步走出的最大值，我们使用单调队列。
首先求出循环节的前缀和sum，单调队列维护长度为p的滑窗的sum最小值。
维护  ans =（ sum[i]-单调队列最小值 ） 的最大值就可以啦！
由于p的长度，要把循环节扩展3倍哟。


然后我们看到，这个单调队列，在ans取得最大值时，单调队列的最小值位置是不定的，所以很容易想到，不一定就是循环节找出来时的起点，所以我们很容易想到，这一个过程，相当于已经枚举了实际问题中的起点。
也就是，我们在取ans的最大值时的最小值位置，就可以当实际问题中的起点。

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100086;
const int maxm = 100086;
const int inf = 2.1e9;
const ll Inf = 999999999999999999;
const int mod = 1000000007;
const double eps = 1e-6;
const double pi = acos(-1);
ll num[maxn];
vector<ll>vec;
bool vis[maxn];
ll sum[maxn];
ll n,s,m,k;
int len;
struct node
{
    ll x;
    int id;
};
deque<node>q;
ll solve(int p){
    q.clear();
    for(int i=0;i<len;i++){
        vec.push_back(vec[i]);
    }
    for(int i=0;i<len;i++){
        vec.push_back(vec[i]);
    }
    ll ans=0;
    sum[0]=vec[0];
    for(int i=1;i<len*3;i++){
        sum[i]=sum[i-1]+vec[i];
    }
    for(int i=0;i<len*3;i++){
        while(!q.empty()&&q.back().x>sum[i]){
            q.pop_back();
        }
        if(!q.empty()&&q.front().id<i-p){q.pop_front();}
        q.push_back(node{sum[i],i});
        ans=max(ans,1ll*sum[i]-q.front().x);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    int cases=0;
    while(T--){
        ll ans=0;
        cases++;
        scanf("%lld%lld%lld%lld",&n,&s,&m,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&num[i]);
        }
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            vec.clear();
            if(vis[i]){continue;}
            int pos=i;
            for(int j=1;j<=m;j++){
                vec.push_back(num[pos]);
                vis[pos]=true;
                pos+=k;
                if(pos>n){pos%=n;}
                if(vis[pos]){break;}
            }
            len=vec.size();
            ll sum=0;
            for(int i=0;i<len;i++){
                sum+=vec[i];
            }
            if(sum<0){
                ans=max(ans,solve(len));
            }
            else{
                ans=max(ans,solve(m-(m/len-1)*len)+(m/len-1)*sum);
            }
        }
        printf("Case #%d: %lld
",cases,max(0ll,s-ans));
    }
    return 0;
}

View Code