题目背景 : 小组内的作业题 — 样例太水了!

在我做这道题之前,小组内就已经有人给出了正解:
TIM截图20181101150526.png

于是,我就写了一个单调队列,没想到,十分轻易地过了样例

然后就是 tcl 的惨案 : 秒过样例0分!

然后就调出题解来看了看,然后进行了修改…

code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 110000
#define ll long long
namespace tql{
    ll n , k , a[maxn] ,f[maxn] ,head = 1,tail = 1 ,q[maxn] ,p[maxn] ;
    ll read() {
        ll x = 0;ll f = 1;ll s = getchar() ;
        while(s>'9'||s<'0') {if(s=='-')f=-1;s=getchar();}
        while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();}
        return x*f ;
    }
    ll max(ll a,ll b) {
        return a>b? a :b ;
    } 
}

using namespace tql ;

int main () {
    n = read() , k = read() ;
    ll tot=0 ,ans = 0;
    for(ll i= 1 ; i <= n ; i ++) {
        a[i] = read () ;tot += a[i] ;
    }
    for(ll i = 1 ; i <= n ; i ++) {
        f[i] = q[head] + a[i] ;
        while(head<=tail&&f[i]<=q[tail]) tail --;q[++tail] = f[i],p[tail] = i ;
        while(head<=tail&&p[head] < i-k ) head ++ ;
    }
    for(ll i = n-k ; i <= n ; i ++) ans = max(ans,tot-f[i]) ; 
    printf("%lld\n",ans) ;
    return 0 ;
}

完结!!!