Z_L_G

题解

总结(8) 训练赛(3)

/ 注册

全部文章 / 题解（共2篇）

算法入门-01分数规划

定义有n个物品，每个物品有价值和消耗，从其中拿k个，希望使得 ∑价值/∑消耗最大方法设最优解X=∑v/∑c，对式子做变形有∑v-X∑c=0，再变形有∑(v-Xc)=0 易发现这是一个单调式子，故考虑使用二分二分X，每次计算当前X下的(v-Xc)，取前k个求∑(v-Xc)，如果小于0则...

二分答案 01分数规划

2025-03-19

0 22

算法入门-第K大和第M大

题意给定一个长为n的数组a，对于他的每个区间拿出他的第K大元素，将所有的第K大元素进行排序，请问其中的第M 大是多少思路转化1：第K大数比X小的区间个数不能超过M-1个转化2：区间中大于等于X的元素超过K个的区间小于M个转化3：二分M，按上述要求检查所有可能的区间转化4：对于找区间...

二分答案

2025-03-17

0 20