• 2024-10-20abc376E Max x Sum
    有序列A[N]和B[N],选出一组大小为K的下标,让A[i]的最大值乘以(B[i]之和)的结果最小,求最小值。1<=T<=2E5,1<=K<=N<=2E5,1<=A[i],B[i]<=1E6分析:因为A[i]跟B[i]要同步选,因此对下标排序,然后枚举每个A[i]作为最大值,从B[i]中选出最小的K个求和,得到结果,B[i]之和可以用堆来维护。#inclu
  • 2024-10-20[ABC376E] Max × Sum 题解
    [ABC376E]Max×Sum题解原题链接洛谷链接一道简单的推性质题,首先明确一个性质,子集是非连续的,所以在计算时并不用连续区间求。拿过题来,首先想的是枚举\(B\)的最小子集,但其复杂度为\(O(C_N^K)\)复杂度过高,不足以通过本题。于是转变思路,枚举\(A\)之中的最大值。若\(a_i