USACO08NOV玩具Toys

发表于
  • 题意
    餐巾计划问题（费用流经典题），数据加强（$1 \le N \le 10^5$）。

  • Solution
    设$f(x)$代表购买$x$个新玩具所需要的最小花费，那么$f$是一个单峰的函数，可以使用三分法求解。
    $f(x)$可以通过贪心的方法求出，这个稍后详细介绍。

  • 接下来简单说明一下这个单峰。假设当$x=t$时有最优解$f(t)$。若取$x = t+1$，那么就会多了一个新买的玩具没有用，浪费了，不会出现更优解，不难发现当$x = t + k ( k \in N^* )$，该结论均成立；若取$x = t - 1$，考虑使用费用流求解时，也就是有有一条在最短路上的边没有走，可能走的是其他最短路径或者次短路，也不会出现更优解，$x = t-k$时类似。

  • 然后说说贪心法计算$f(x)$。为了方便描述，不妨设$c1 \le c2$不难发现，当前所需要的玩具，首先应该考虑已经购买但是还没有使用的新玩具，因为额外花费为0；在这之后，再考虑便宜点的$c1$，而且是离当前越近越好，因为再往前的天数可能没有足够的脏玩具用来洗；最后再考虑贵的$c2$，这时候应该离当前越远越好，因为越往前靠的话，洗好的玩具就有更大的机会用来用$c1$洗，可以为以后减少花费。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1e5+5, zhf = 0x3f3f3f3f ;
int n, m, t[maxn], s[maxn], tc, n1, n2, c1, c2 ;
struct node {
    int id, val ;
} ;
deque <node> Q ;
int calc ( int x ) {
    int rec = (tc - c2)*x, i, k ;
    node tmp ;
    Q.clear() ;
    Q.push_front( (node){-n2, x} ) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        m = t[i] ;
        if ( i - n1 >= 1 ) Q.push_front( (node){i - n1, t[i - n1]} ) ; 
        while(m) {
            if ( Q.empty() ) return zhf ;
            tmp = Q.back() ;
            if ( tmp.id + n2 <= i && c1 > c2 ) {
                k = min(m, tmp.val) ;
                m -= k ; tmp.val -= k ;
                rec += k*c2 ;
                Q.pop_back() ;
                if ( tmp.val ) Q.push_back(tmp) ;
            } else {
                tmp = Q.front() ;
                k = min(m, tmp.val) ;
                m -= k ; tmp.val -= k ;
                rec += k*c1 ;
                Q.pop_front() ;
                if ( tmp.val ) Q.push_front(tmp) ;
            }
        }
    }
    return rec ;
}
int main() {
    int i, k, l = 1, r = 0, mid1, mid2 ;
    Read(n) ; Read(n1) ; Read(n2) ; Read(c1) ; Read(c2) ; Read(tc) ;
    if ( n1 > n2 ) swap(n1, n2), swap(c1, c2) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(t[i]) ;
        r += t[i] ;
    }
    while ( r - l > 20 ) {
        mid1 = (l*2 + r)/3 ;
        mid2 = (l + r*2)/3 ;
        if ( calc(mid1) >= calc(mid2) ) l = mid1 ;
        else r = mid2 ;
    }
    k = zhf ;
    for ( i = l ; i <= r ; i ++ )
        k = min(k, calc(i)) ;    
    printf ( "%d\n", k ) ;
    return 0 ;
}