贪心类排序问题如没思路，请熟练掌握DFS取保底分！配合记忆化效果更佳

B3874 [GESP202309 六级] 小杨的握手问题

题意

  • 逆序对：数组中对i,j位置的两个数a[i],a[j]，若满足i < j 且a[i] > a[j]，称为一个逆序对，即前大后小的数对。

  • 本题等价求顺序对：$(i<j)$ 并且 $a[i] < a[j]$ 的数对总个数。
    总全部数对：$total = n*(n-1)/2$>

    小技巧：顺序对 = 全部两两数对 − 逆序对；可以直接复用归并求逆序对代码，用减法得到答案。

标准做法：归并排序（分治）求顺序对

  • 归并排序代码模板请站内自行搜索
    归并排序分两半：左半区间[l,mid]，右半区间[mid+1,r]
    顺序对分为3部分：
  1. 两个数都在左半 →递归左半求解
  2. 两个数都在右半 →递归右半求解
  3. 一个数在左半，一个数在右半（跨区间，归并合并阶段统计）

合并阶段核心统计（跨区间顺序对）

左数组指针i，右数组指针j
当 a[i] < a[j]：
此时右数组从 j 到末尾全部元素，都比当前a[i]大。
左的这个a[i]，可以和右边 r‑j+1 个数字构成顺序对。

if(a[i] < a[j]){
    ans += r - j + 1;   //核心计数语句
    tmp[k++] = a[i++];
} else {
    tmp[k++] = a[j++];
}

原理说明

  1. 归并的时候左右两段内部已经分别排好序。
  2. 如果左边的a[i]小于右边a[j]，因为右半有序，a[j],a[j+1],…,a[r]全部 ≥ a[j]，因此都大于a[i]。
  3. 这些全部是合法顺序对，i在左、j系列在右，天然满足下标 (i<j)，直接一次性累加数量，不用一对一对枚举。
  4. 递归处理左右内部顺序对，合并阶段统计跨区间顺序对，总和就是全部顺序对。

P11247 [GESP202409 六级] 算法学习

题意

一共有m种算法，n道题；每道题属于某一个算法，做题提升该算法熟练度。
要求：

  1. 每种算法熟练度至少k；
  2. 不能连续做同一知识点的题；
    求最少做题数量，无解输出-1。

核心两步思路

第一步：贪心选出每种算法最少要做多少道题

对全部题目按照b值从大到小排序。
对每个算法i，优先选提升大的题目，凑到熟练度≥k；得到need[i]：算法i达标的最少题目数量。

如果某个算法全部题目加起来仍然达不到k →直接无解输出‑1。
ans = sum(need[i])：不考虑“不能连续相同”限制下，总最小题数。

第二步：调度约束（不能连续相同，经典重排间隔问题）

设 max_need = 所有need[i]里面的最大值。
经典结论：把一批元素重新排列，相同元素不能相邻，可行的充要条件：

其余所有元素总和 ≥ max_need − 1
也就是：ans − max_need ≥ max_need − 1
  1. 如果条件成立：直接输出ans，原来选出来的这些题就可以排开，不需要额外做题。

  2. 如果条件不成立：
    最少总题数必须扩充到 required_total = 2 * max_need − 1。
    需要额外补 need_add = required_total − ans 道题目。

    补充的题目只能从别的算法剩余没选过的题里面拿，不能用已经计入need[i]的题。
    extra_available：其他算法，总题目 − 已经选的need[i]，即可拿来填充的备用题。
  3. 如果extra_available >= need_add：输出2*max_need‑1
  4. 否则：无论怎么加，都无法隔开最多的那一类，输出‑1

原理拆解

  1. 贪心阶段：要总题数尽可能少，每种算法内部一定优先选b最大的题目，用最少题把熟练度顶到k。
  2. 重排模型：最多的一类有max_need道，至少需要max_need‑1道别的题插在它们之间隔开。
    例：A A A →需要至少2个别的插缝 A X A X A，总长度最少5=2*3‑1。
  3. 不够插缝时，就要额外多做一些别的算法的题目充当“填充物”，只用来隔开，不改变熟练度（已经达标）；没有足够备用题目就无解。

样例1：
m=3，need[1]=2，need[2]=1，need[3]=1。
ans=4，max_need=2。
ans‑max_need =2 ≥ 2‑1=1，条件成立，直接输出4。

样例2：
m=2，算法1最少需要3题，算法2最少需要1题。ans=4，max_need=3。
ans‑max_need=1，max_need‑1=2，1<2。需要扩充到2*3‑1=5。
需要补1道额外题；但算法2已经没有多余题目，extra_available=0，不够，输出‑1。

P11376 [GESP202412 六级] 运送物资

题意

数轴：A市0，B市x；站点坐标$p$。
一辆车放在$p$：

  • 去A一趟路程：$2p$
  • 去B一趟路程：$2(x-p)$

货车$i$：A跑$a_i$次，B跑$b_i$次。
总路程 = $2\cdot a_i\cdot p + 2\cdot b_i\cdot(x-p)$。
每个站点$p_i$最多放$c_i$辆车；一共$m$辆货车，分配到站点，求全部货车总路程最小。

对一辆货车，整理公式：

$$ \begin{aligned} \text{cost} &=2 a p + 2b(x-p) \\ &=2bx + 2p(a-b) \end{aligned} $$

$2bx$是常数，和站点$p$无关；
变量部分：$2\cdot p\cdot (a_i-b_i)$。

目标：最小化总和，常数项可以最后统一加，只看 $p\times (a_i-b_i)$。

贪心原理

  1. 如果 $a_i - b_i > 0$（A跑的次数更多）：系数为正。想要总代价小，p要尽可能小，放到靠左的站点。
  2. 如果 $a_i - b_i < 0$（B跑的次数更多）：系数为负。想要总代价小，p要尽可能大，放到靠右的站点。
  3. $a_i-b_i=0$：p不影响代价，放哪里都行。

排序规则：

  • 货车A偏多（$a\ge b$）：按 $(a_i-b_i)$ 从大到小排序。差值越大，越优先拿最左边剩余的站点。
  • 货车B偏多（$a< b$）：按 $(b_i-a_i)$ 从大到小排序。差值越大，越优先拿最右边剩余的站点。
  • 站点按坐标从小到大排序。

分配：

  1. A偏多货车，从左向右取站点空位；
  2. B偏多货车，从右向左取站点空位；
    每分配一辆，该站点容量$c_i$减1；计算路程累加到sum。

关键公式拆解（代码累加部分）

  • sum += 2LL questl[i].left stat[cur].place + 2LL questl[i].right (dist‑stat[cur].place);

等价：
$2\cdot a\cdot p + 2\cdot b\cdot (x-p)$，

样例简单理解

站点：(1,1) (2,1) (8,3)，x=10
货车4辆：

  1. 5 3 →a‑b=2>0，A偏多
  2. 7 2 →a‑b=5>0，A偏多
  3. 9 0 →a‑b=9>0，A偏多
  4. 1 10000 →a‑b<0，B偏多

A偏多三辆按差值降序：(9,0) > (7,2) > (5,3)
优先拿左边空位：
(9,0)放p=1；(7,2)放p=2；剩下(5,3)，左边用完，只能拿右边p=8。
B偏多那辆放最右侧p=8。
算出总和40186，和样例输出一致。

代码思路

  1. 读入n,m,x；读入站点$(p_i,c_i)$。

  2. 读每一辆货车$(a_i,b_i)$：

    • $a_i \ge b_i$归入questl（A偏多）
    • $a_i < b_i$归入questr（B偏多）
  3. 站点按place从小到大sort；
    questl按$(a-b)$降序；questr按$(b-a)$降序。
  4. cur从1开始处理questl：不断取当前最左边还有容量的站点，分配一辆车，$c$减一，累加路程。
  5. cur从n开始处理questr：不断取当前最右边还有容量的站点，分配一辆车，$c$减一，累加路程。
  6. 输出sum。

复杂度

$O(n\log n + m\log m)$，适配 $10^5$。

易错坑点

  1. 全部乘法必须强转long long，$p,x,a_i,b_i$数值很大，int直接相乘溢出；代码中2ll就是为了提升到64位。
  2. 分配的时候要跳过已经用完容量$c_i=0$的站点，移动指针cur，不能每次从头遍历。
  3. 不要把公式推错；不要搞反：A多的车要靠左，B多的车要靠右。

部分分思路（暴力，仅很小数据）

枚举每一辆车分配哪个站点，多重循环，大数据超时，只能过小数据。

标签: none

评论已关闭