题目大意
有一个长为 n n n的序列 a i a_i ai,你可以选择一个 i i i花费 c x c_x cx元 ( x ∈ [ 1 , m ] ) (x\in[1,m]) (x∈[1,m])将 a i a_i ai变为 ⌊ a i x ⌋ \lfloor\dfrac{a_i}{x}\rfloor ⌊xai⌋,你总共有 K K K元,求最终序列的中位数最小是多少。保证 n n n为奇数。
1 ≤ n , m ≤ 5 × 1 0 5 , 1 ≤ a i ≤ m , 1 ≤ c i , K ≤ 1 0 9 1\leq n,m\leq 5\times 10^5,1\leq a_i\leq m,1\leq c_i,K\leq 10^9 1≤n,m≤5×105,1≤ai≤m,1≤ci,K≤109
题解
首先,我们知道 ⌊ ⌊ t x ⌋ y ⌋ = ⌊ t x y ⌋ \lfloor\dfrac{\lfloor\frac tx\rfloor}{y}\rfloor=\lfloor\dfrac{t}{xy}\rfloor ⌊y⌊xt⌋⌋=⌊xyt⌋,那么我们可以用 c i × j = min ( c i × j , c i + c j ) c_{i\times j}=\min(c_{i\times j},c_i+c_j) ci×j=min(ci×j,ci+cj)来更新所有 c c c值,这样我们就可以得到用若干次除法将 a i a_i ai除以一个数的最小代价。更新所有 c c c值的时间复杂度为 O ( ∑ i = 1 m m i ) = O ( m ln m ) O(\sum\limits_{i=1}^m\dfrac mi)=O(m\ln m) O(i=1∑mim)=O(mlnm)。
二分答案 m i d mid mid,我们需要让 ⌈ n 2 ⌉ \lceil\dfrac n2\rceil ⌈2n⌉个 a i a_i ai都小于等于 m i d mid mid。对于每个 a i a_i ai,我们可以二分求出最小的 x 0 x_0 x0使得 ⌊ a i x 0 ⌋ ≤ m i d \lfloor\dfrac{a_i}{x_0}\rfloor\leq mid ⌊x0ai⌋≤mid,那么我们取 x ≥ x 0 x\geq x_0 x≥x0即可使得 ⌊ a i x ⌋ ≤ m i d \lfloor\dfrac{a_i}{x}\rfloor\leq mid ⌊xai⌋≤mid,我们在大于等于 x 0 x_0 x0的 x x x中取 c x c_x cx的最小值,预处理一个后缀最小值即可。
求出将每个 a i a_i ai降到 ≤ m i d \leq mid ≤mid的最小代价 w i w_i wi后,将 w i w_i wi从小到大排序,然后取代价最小的 ⌈ n 2 ⌉ \lceil\dfrac n2\rceil ⌈2n⌉个 w i w_i wi,,记这些 w i w_i wi的和为 s u m sum sum。如果 s u m ≤ K sum\leq K sum≤K,则 m i d mid mid合法;否则, m i d mid mid不合法。
这样做的话,时间复杂度为 O ( n log m log n ) O(n\log m\log n) O(nlogmlogn)。我们考虑优化。
我们可以先将 a i a_i ai从小到大排序,那么随着 a i a_i ai的增加, x 0 x_0 x0也是单调不降的,那么我们用一个双指针就可以 O ( n ) O(n) O(n)求出所有 a i a_i ai对应的 x 0 x_0 x0,并求出将这个 a i a_i ai降到 ≤ m i d \leq mid ≤mid的最小代价 w i w_i wi。我们发现,此时 w i w_i wi也是单调不降的,于是就不用排序了。一次判断 m i d mid mid是否合法的时间复杂度为 O ( n ) O(n) O(n),那么总时间复杂度为 O ( n log m ) O(n\log m) O(nlogm)。
因为中位数可能为 0 0 0,所以需要求除数大于 m m m的情况,可以将这类情况的最小代价存储在 c m + 1 c_{m+1} cm+1中。具体操作见代码。
总时间复杂度为 O ( m ln m + n log m ) O(m\ln m+n\log m) O(mlnm+nlogm)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=500000;
int n,m,k,a[N+5],c[N+5],s[N+5],w[N+5];
bool check(int mid){int x=1;for(int i=1;i<=n;i++){if(a[i]<=mid){w[i]=0;continue;}while(a[i]/x>mid) ++x;w[i]=s[x];}int tmp=0;for(int i=1;i<=n/2+1;i++){tmp+=w[i];if(tmp>k) return 0;}return 1;
}
int main()
{
// freopen("opt.in","r",stdin);
// freopen("opt.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=m;i++){scanf("%d",&c[i]);}sort(a+1,a+n+1);for(int i=1;i<=m;i++){for(int j=2;j<=i&&i*j<=m;j++){c[i*j]=min(c[i*j],c[i]+c[j]);}}s[m]=c[m];s[m+1]=1e9+1;for(int i=m-1;i>=1;i--) s[i]=min(s[i+1],c[i]);for(int i=1;i<=m;i++){for(int j=2;j<=i;j++){if(i*j>m){s[m+1]=min(s[m+1],s[i]+s[j]);break;}}}for(int i=m;i>=1;i--) s[i]=min(s[i+1],s[i]);int l=0,r=m,mid;while(l<=r){mid=l+r>>1;if(check(mid)) r=mid-1;else l=mid+1;}printf("%d",r+1);return 0;
}