2010-1128

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

'''题目描述：'''[[BR]]

幽幽子和妖梦要开个hanami party，妖梦她每天能干两件事，1.练级——等级L++，2.做菜——做L个菜。但幽幽子每天都需要吃a[i]个菜。问在满足幽幽子每天都有足够的菜吃的情况下，n天后能有多少个菜。[[BR]]



'''解题方法：'''[[BR]]

首先如果练级的话，越早练越好。[[BR]]

于是我们可以让她在满足条件的情况下尽量练级。[[BR]]

然后从最后一次练级开始往前推，一个一个把练级改为做菜，每一次改变都会增加做菜量，直到有一天改变之后，做菜总量减少为止。[[BR]]

这时的做菜总量就是最大的做菜总量。[[BR]]

下面是作者猛犸也钻地的标程[[BR]]


{{{
#!cpp
#include <cstdio>
#include <stack>
using namespace std;

int main(){
    int n, l, v;
    while (scanf("%d%d", &n, &l) > 0){
        long long a[100001], s = 0;
        stack <int> q;
        a[0] = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d", &v);
            a[i] = a[i - 1] + v;
        }
        for (int i = 1; i <= n; i++){
            q.push(i);
            while(!q.empty() && (s < a[i] || i == n)){
                v = (l + q.size() - 1) - (i - q.top());
                if(v <= 0) 
                    break; 
                else 
                    s += v;
                q.pop();
            }
            if (s < a[i]) 
                break;
        }
        if (s < a[n]) 
            printf("Myon\n"); 
        else 
            printf("%lld\n", s - a[n]);
    }
}

}}}

用了一个栈来记录那些日子用来练级，这样处理起来就很方便。

题目描述：

幽幽子和妖梦要开个hanami party，妖梦她每天能干两件事，1.练级——等级L++，2.做菜——做L个菜。但幽幽子每天都需要吃a[i]个菜。问在满足幽幽子每天都有足够的菜吃的情况下，n天后能有多少个菜。

解题方法：

首先如果练级的话，越早练越好。

于是我们可以让她在满足条件的情况下尽量练级。

然后从最后一次练级开始往前推，一个一个把练级改为做菜，每一次改变都会增加做菜量，直到有一天改变之后，做菜总量减少为止。

这时的做菜总量就是最大的做菜总量。

下面是作者猛犸也钻地的标程

#include <cstdio>
#include <stack>
using namespace std;
int main(){
    int n, l, v;
    while (scanf("%d%d", &n, &l) > 0){
        long long a[100001], s = 0;
        stack <int> q;
        a[0] = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d", &v);
            a[i] = a[i - 1] + v;
        }
        for (int i = 1; i <= n; i++){
            q.push(i);
            while(!q.empty() && (s < a[i] || i == n)){
                v = (l + q.size() - 1) - (i - q.top());
                if(v <= 0) 
                    break; 
                else 
                    s += v;
                q.pop();
            }
            if (s < a[i]) 
                break;
        }
        if (s < a[n]) 
            printf("Myon\n"); 
        else 
            printf("%lld\n", s - a[n]);
    }
}

用了一个栈来记录那些日子用来练级，这样处理起来就很方便。