menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[贪心+树状数组]COCI2012【RASPORED】题解
apps COCI
local_offer 查看标签
comment 0 条评论

题目概述

\(n\) 个任务,第 \(i\) 个任务需要 \(T_i\) 的时间完成,加分为 \(L_i-s_i\) ,其中 \(s_i\) 表示完成该任务的时间。有 \(q\) 组修改,会变动 \(L_i\)\(T_i\) ,问未修改时的最优解和每次修改之后的最优解。

解题报告

\(s_i\)\(T_i\) 表示,假设完成顺序为 \(\{ID_n\}\) ,那么答案就是 \(\sum L_i-\sum\sum_{i=1}^{n}T_{ID_i}\)

\(\sum L_i\) 是固定的,我们需要安排一个顺序使得后面的式子最小,最优解显然是 \(T_i\) 从小到大。

多组数据用树状数组维护就行了。

示例程序

版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up