洛谷P12000

发表于

题目：P12000 扶苏出勤日记
（第一道绿题纪念）

代码如下（燃尽了，题解缓缓再发）：

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
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1000010], b[1000010], p[1000010];

bool ck(int n, int x)
{
    int money = 0, coin = 0;
    for (int i = 1; i <= n; i++)
    {
        money += b[i];
        if (p[i])
        {
            if (coin < 1ll * (p[i] - i) * x)
            {
                int t = 1ll * (p[i] - i) * x - coin;
                int cost = min((t + a[i] - 1) / a[i], money);
                coin += cost * a[i];
                money -= cost;
            }
        }
        else
        {
            coin += money * a[i];
            money = 0;
        }
        coin -= x;
        if (coin < 0) return 0;
    }
    return true;
}

int fid(int n)
{
    int left = 1, right = 1e12, ans = 0;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (ck(n, mid))
        {
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        stack<int> s;
        for (int i = n; i >= 1; i--) 
        {
            while (!s.empty() && a[s.top()] <= a[i])
                s.pop();
            p[i] = s.empty() ? 0 : s.top();
            s.push(i);
        }
        cout << fid(n) << "\n";
    }
    return 0;
}