主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:AT_abc416_d [ABC416D] Match, Mod, Minimize 2
最后更新于 2025-07-31 14:09:16
作者
zhoujunchen
分类
题解
题解
AT_abc416_d
复制 Markdown
查看原文
删除文章
更新内容
题目说 $0\le A_i,B_i <M$,有两种情况。 1. $A_i+B_i <M$,对答案贡献为 $A_i+B_i$。 2. $A_i+B_i\ge M$,即 $M\le A_i+B_i<2M$,对答案贡献为 $A_i+B_i-M$。 所以对答案的贡献不是 $A_i+B_i$ 就是 $A_i+B_i-M$。 答案的柿子就变成了这样: $$(\sum_{i=1}^N(A_i+B_i))-kM$$ 其中 $k$ 是有多少对 $A_i+B_i\ge M$。 为了让答案最小,即 $k$ 要尽可能地大。 我们可以先排序,然后用双指针来求。 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long int n,m,a[314514],b[314514],ans; void fkM28(){ ans=0; cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i],ans+=a[i]; for(int j=1;j<=n;j++)cin>>b[j],ans+=b[j]; sort(a+1,a+n+1),sort(b+1,b+n+1); for(int i=1,j=n;i<=n;i++) if(a[i]+b[j]>=m) j--,ans-=m; cout<<ans<<"\n"; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--)fkM28(); return 0; } ```
正在渲染内容...
点赞
0
收藏
0