AtCoderBeginnerContest308 F 問題 500 点「Vouchers」

問題概要

制約

解法

この問題は，どのようなクーポンと商品の組合せでも割り引かれる値は d だけなので，できるだけ$\sum D_i$を大きくするかという問題になる。 $P_i$の小さいものから見ていく。$P_i$に適用可能なクーポンのうち，最も$D_i$の大きなクーポンを利用して割り引く。 P を降順に見ていくと，もっと小さい P で使用できたクーポンを無駄に使うことになり，結果として$\sum D_i$が小さくなるためだめ。クーポンの管理は，$L_i$が小さい順にソートし，$P_i \ge L_i$を満たす$D_i$だけ優先度付き queue に入れておけば良い。最大値の取得と削除ができれば良いので，SortedMultiSet でもよい。 Rust の場合は，sortedmultiset がないので hashmap と btreeset で管理することになって面倒なので，素直に binaryheap を使用したほうが実装が用意。

お気持ち

AC コード

from collections import deque
from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
P = list(map(int, input().split()))
L = list(map(int, input().split()))
D = list(map(int, input().split()))

P.sort()
heap = []
heapify(heap)
ans = 0
LD = [(l, d) for l, d in zip(L, D)]
LD.sort()
que = deque(LD)

for p in P:
    while que:
        l, d = que.popleft()
        if l <= p:
            heappush(heap, -d)
        else:
            que.appendleft((l, d))
            break
    if heap:
        d = heappop(heap)
        ans += p + d
    else:
        ans += p
print(ans)

#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
#![recursion_limit = "1024"]
use std::collections::{vec_deque, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::f64::consts::PI;
use std::mem::swap;
use std::process::exit;
use std::{isize, println};

use itertools::{CombinationsWithReplacement, Itertools};
use num::{integer::Roots, traits::Pow, ToPrimitive};
use num_integer::{div_ceil, Integer};
use num_traits::{abs_sub, Float};
use permutohedron::Heap;
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::io::*;
use whiteread::parse_line;
//

fn solve() {
    input! {
        N:usize, M:usize,
        mut P:[usize; N],
        L:[usize; M],
        D:[usize; M]
    }
    let mut que = VecDeque::new();
    let mut heap = BinaryHeap::new();
    let mut LD = vec![];
    for i in 0..M {
        let l = L[i];
        let d = D[i];
        LD.push((l, d));
    }
    LD.sort();
    for &v in LD.iter() {
        que.push_back(v);
    }
    P.sort();
    let mut ans = 0;
    for &p in P.iter() {
        while !que.is_empty() {
            let (l, d) = que.pop_front().unwrap();
            if l <= p {
                heap.push(d);
            } else {
                que.push_front((l, d));
                break;
            }
        }
        if heap.is_empty() {
            ans += p;
        } else {
            let d = heap.pop().unwrap();
            ans += p - d;
        }
    }
    println!("{}", ans);
}

fn main() {
    // input! {N:usize}
    // for _ in 0..N {
    //     solve();
    // }
    solve();
}

AtCoderBeginnerContest308 F 問題 500 点 「Vouchers」

問題概要

制約

解法

お気持ち

AC コード

AtCoderBeginnerContest308 F 問題 500 点「Vouchers」