2023NOIP A层联测31 暴力操作

news/2024/11/29 2:40:55/

题目大意

有一个长为 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 1n,m5×105,1aim,1ci,K109


题解

首先,我们知道 ⌊ ⌊ t x ⌋ y ⌋ = ⌊ t x y ⌋ \lfloor\dfrac{\lfloor\frac tx\rfloor}{y}\rfloor=\lfloor\dfrac{t}{xy}\rfloor yxt=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=1mim)=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 x0aimid,那么我们取 x ≥ x 0 x\geq x_0 xx0即可使得 ⌊ a i x ⌋ ≤ m i d \lfloor\dfrac{a_i}{x}\rfloor\leq mid xaimid,我们在大于等于 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 sumK,则 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;
}

http://www.ppmy.cn/news/1216942.html

相关文章

centralwidget 不能布局

必须要在QT ui中添加一个任意的子控件&#xff08;比如添加了一个pushButton&#xff09;&#xff0c;然后在centralwidget 才能右键设置布局&#xff0c;成功去掉centralwidget 右下角的红色的标记。

桌面便签软件用哪个?10款全球好用的便签软件推荐,告别杂论无章!

在如今的快节奏社会中&#xff0c;我们的生活和工作节奏越来越快&#xff0c;每天面对的信息成倍地增长。有时候&#xff0c;我们需要随手记下一些重要的事情&#xff0c;或者是一些突然的灵感&#xff0c;这时候就需要一款好用的桌面便签软件。 桌面便签软件可以帮助我们更好…

《线性代数》科教版教材必会习题

出一期比较尴尬的博客——有关线代教材的课后题总结~ 之所以说尴尬&#xff0c;主要有两个主要原因&#xff1a;这本科教版第三版的教材&#xff0c;整体看起来并不是那么舒服&#xff0c;甚至被我们的老师吐槽过&#xff0c;更好地选择时同济版的那本紫书——我们学校的新生这…

动作活体检测能力支持自定义扫描动作,开发者接入更高效

随着人脸识别技术在金融、医疗等多个领域的加速落地&#xff0c;网络安全、信息泄露等问题愈为突出&#xff0c;用户对应用稳定性和安全性的要求也更为严格。 华为机器学习服务的动作活体检测能力&#xff0c;支持实时捕捉人脸&#xff0c;根据用户配合做动作可以判断是真实活…

Spring Boot 拦截器 HandlerInterceptor的使用以及WebMvcConfigurer简单介绍

当我们使用Spring Boot构建Web应用程序时&#xff0c;HandlerInterceptor 是一个重要的组件&#xff0c;用于拦截请求的处理过程。HandlerInterceptor 接口定义了在请求处理的不同阶段执行的方法&#xff0c;允许我们在请求到达处理程序之前和之后执行自定义逻辑。 HandlerInt…

TCP和UDP C#代码实战

网络传输的七层结构&#xff1a; 其中TCP和UDP协议在传输层。 TCP/IP协议 TCP/IP中包含了四层架构中的多个协议&#xff0c;取其中两个进行了命名&#xff1a; TCP TCP的特点 粘包问题处理 TCP一次性接收过多数据必然出现粘包&#xff0c;即不同时发送的数据黏连在一…

Microsoft Forms

Microsoft Forms官网&#xff1a;Microsoft Forms - Free tool to create online surveys, forms, polls, and quizzes Microsoft Forms主要用来自定义一些表单和问卷调查 点击新建表单 填写完表单名称之后&#xff0c;下面就可以添加问题了&#xff0c;可以选择多种提问方式…

Windows装机必装软件|每款都好用到起飞!

1.GeekUninstaller&#xff1a;这款软件是一款功能强大的卸载工具&#xff0c;可以完全删除无用的程序和插件&#xff0c;并清理与之相关的文件夹。它没有广告或捆绑软件&#xff0c;非常干净。 2.PotPlayer&#xff1a;作为一款纯粹的播放器&#xff0c;PotPlayer可以流畅播放…