主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:AT_abc416_d [ABC416D] Match, Mod, Minimize 2
最后更新于 2025-07-31 11:44:43
作者
weifengzhaomi
分类
题解
题解
AT_abc416_d
复制 Markdown
查看原文
删除文章
更新内容
### 闲话 终于能稳切 $D$ 题了!发个题解纪念纪念。 ## 题意 题目意思简单来讲就是有两个序列,其中第一个序列可以任意排序,第二个序列不能动,然后,我们将第一个数组排好序后,然后两个数组相同的位置的数相加取模题目的模数,要使得结果最小。 ## 思路 首先,我们发现,其实我们可以任意移动第二个数组,为什么呢? 因为呀,第一个数组可以移到任意一个位置,所以,我们移动第二个数组其实等于不动,然后第一个数组跟着第二个数组移动。 然后,我们发现,第一个数组和第二个数组排序后可以用**贪心和双指针**! 这又是为什么呢? 因为呀,我们是用双指针来模拟当前第二个数组的值加上那个第一个数组的值哪里好。 而我们的数组排好序后,一定是有序的,答案只能是数组第一个指针的位置或最后一个指针的位置。 而贪心可以帮助我们寻找最优解。 当前的选择,不会影响到后面的结果。 所以这就是为什么贪心和双指针是正确的。 ## 代码: ```cpp #include<bits/stdc++.h> using namespace std; long long t,n,m,ans,l,r,top,a[300010],b[300010]; bool cmp(long long x,long long y){ return x > y; } int main(){ cin >> t; while (t--){ scanf("%lld%lld",&n,&m),ans = 0,top = 1,l = 1,r = n; for (int i = 1;i <= n;i++) scanf("%lld",&a[i]); sort(a + 1,a + n + 1,cmp); for (int i = 1;i <= n;i++) scanf("%lld",&b[i]); sort(b + 1,b + n + 1); while (l <= r){ if ((b[top] + a[l]) % m < (b[top] + a[r]) % m) ans += (b[top] + a[l]) % m,l++; else ans += (b[top] + a[r]) % m,r--; top++; } printf("%lld\n",ans); } } ```
正在渲染内容...
点赞
0
收藏
0