跳转至

CF609D

知识点

  • 二分
  • two pointers
  • 前缀和

题意简述

你在 \(n\) 天的时间内有 \(m\) 个物品供你购买。你有 \(s\) 元人民币,但物品要么只能用美元支付(\(t_i = 1\))、要么只能用英镑支付(\(t_i = 2\))。

给定这 \(n\) 天内每天人民币对美元的汇率 \(a_i\)、对英镑的汇率 \(b_i\),以及每个物品的价格 \(c_i\),你可以在一天买多个物品。求买到 \(k\) 个物品所用最少天数;若买不到 \(k\) 个物品,输出 -11

数据范围:\(1 \le n \le 2\cdot 10^5\)\(1 \le k \le m \le 2\cdot 10^5\)\(1 \le s \le 10^9\)\(1 \le a_i, b_i, c_i \le 10^6\)\(t_i \in \{1, 2\}\)

解题思路

不难看出二分最少天数,然后考虑怎么实现 check() 函数。

显然,我们是在某天最划算的时候去换算两种货币,然后在当天买很多很多东西。

check() 使用的是类似于 two pointers 的做法,先假设全部换成美元,

此时 \(i_1\) 指向最多能买到的美元商品的位置,\(i_2\) 指向英镑商品的头部。

然后在 \(i_1\) 递减的同时 \(i_2\) 尽可能递增,每次看 \(i_1 + i_2\) 能否不小于 \(k\) 即可。

代码实现

核心部分已用高亮标出。

Code
  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
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <bits/stdc++.h>
#define LL long long

namespace io {
    template <typename T> inline void read(T & _x) {
        int f = 0, ch; _x = 0;
        while(!isdigit(ch = getchar())) f |= ch == '-';
        while(isdigit(ch)) _x = _x * 10 + ch - '0', ch = getchar();
        if(f) _x = -_x;
    }
    template <typename T, typename ... Args> inline void read(T &_f, Args& ... args) {
        read(_f), read(args ...);
    }
    inline void _deal(char ch) { putchar(ch); }
    template <typename T> inline void _deal(T _x) {
        if (_x < 0) putchar('-'), _x = -_x;
        if (_x > 9) _deal(_x / 10);
        putchar(_x % 10 + '0');
    }
    inline void write() {}
    template <typename T, typename ... Args> inline void write(T _f, Args ... args) {
        _deal(_f), write(args...);
    }
}

const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
const int M = 2e5 + 5;

int n, m, k, s, a[N] = {inf}, b[N] = {inf}, c[M], mind[N], minp[N];
LL sd[N], sp[N];

int i1, i2, sizd, sizp, d[M], p[M];

bool check(int x) {
    i1 = i2 = 0;
    for(i1 = 1; i1 <= sizd && sd[i1] * a[mind[x]] <= s; ++i1);
    --i1;
    for( ; i1 >= 0; --i1) {
        for( ; i2 <= sizp && sd[i1] * a[mind[x]] + sp[i2] * b[minp[x]] <= s; ++i2);
        --i2;
        if(i1 + i2 >= k)
            return 1;
    }
    return 0;
}

bool cmp(int xx, int yy) {
    return c[xx] < c[yy];
}

int32_t main() {
    io::read(n, m, k, s);
    for(int i = 1; i <= n; ++i) {
        io::read(a[i]);
        if(a[i] < a[mind[i - 1]])
            mind[i] = i;
        else
            mind[i] = mind[i - 1];
    }
    for(int i = 1; i <= n; ++i) {
        io::read(b[i]);
        if(b[i] < b[minp[i - 1]])
            minp[i] = i;
        else
            minp[i] = minp[i - 1];
    }
    for(int i = 1; i <= m; ++i) {
        int t;
        io::read(t, c[i]);
        if(t == 1)
            d[++sizd] = i;
        else
            p[++sizp] = i;
    }
    std::sort(d + 1, d + sizd + 1, cmp);
    std::sort(p + 1, p + sizp + 1, cmp);
    for(int i = 1; i <= sizd; ++i)
        sd[i] = sd[i - 1] + c[d[i]];
    for(int i = 1; i <= sizp; ++i)
        sp[i] = sp[i - 1] + c[p[i]];
    int l = 1, r = n, ans = -1;
    while(l <= r) {
        int mid = l + r + 1 >> 1;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    if(ans == -1)
        puts("-1");
    else {
        io::write(ans, '\n');
        check(ans);
        for(int i = 1; i <= i1 && i <= k; ++i)
            io::write(d[i], ' ', mind[ans], '\n');
        for(int i = 1; i1 + i <= k; ++i)
            io::write(p[i], ' ', minp[ans], '\n');
    }
    return 0;
}