脚本宝典收集整理的这篇文章主要介绍了CF161A - Dress'em in Vests!(暴力+贪心/二分/普及级),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
⇔暴力、⇔贪心、⇔二分、⇔普及级(*1300)
有 (n) 个士兵和 (m) 件背心,给出每个人的体型 (a_i) 和每件背心的大小 (b_i) ,当满足 (a_i-xleq b_jleq a_i+y) 时,说明第 (j) 件背心可以被第 (i) 个人穿上。使得尽可能多的士兵穿上背心,并输出这些匹配对。
对于第 (i) 个士兵,二分查找可供挑选的背心,找到刚好穿上的那一件 (b_j) 。由于数据有序,对于下一个士兵 (i+1) ,他刚好能穿上的那一件大小必定大于 (b_{j+1}) ,故二分查找可供挑选的背心,范围是 (j+1) 到 (m) 。时间复杂度 (O(n*log_2m)) 。
上方的思路已经提到了查找范围的变化,而由于数据是有序的,只要遍历就可以。
对于第 (i) 个士兵,顺序查找可供挑选的背心,找到刚好穿上的那一件 (b_j) 。由于数据有序,对于下一个士兵 (i+1) ,他刚好能穿上的那一件大小必定大于 (b_{j+1}) ,故继续顺序查找可供挑选的背心,范围是 (j+1) 到 (m) 。时间复杂度 (O(n+m)) 。
//A WIDA Project
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int MAX=1e6+5;
LL n, num, m, x, y, w, ans[MAX], Ans[MAX], start = 1, M[MAX], N[MAX], t;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> x >> y;
for(int i = 1; i <= n; i ++) cin >> N[i];
for(int i = 1; i <= m; i ++) cin >> M[i];
for(int i = 1; i <= n; i ++) {
t = lower_bound(M + start, M + 1 + m, N[i] - x) - M;
if(M[t] <= N[i] + y && M[t] != 0) {
num ++;
ans[num] = i;
Ans[num] = t;
start = t + 1;
}
}
cout << num << endl;
for(int i = 1; i <= num; i ++) cout << ans[i] << " " << Ans[i] << endl;
return 0;
}
//A WIDA Project
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int MAX=1e6+5;
LL n, num, m, x, y, w, ans[MAX], Ans[MAX], start = 1, M[MAX], N[MAX], t;
int main() {
cin >> n >> m >> x >> y;
for(int i = 1; i <= n; i ++) cin >> N[i];
for(int i = 1; i <= m; i ++) cin >> M[i];
for(int i = 1; i <= n; i ++) {
while(start <= m && M[start] < N[i] - x) start ++;
if(start <= m && M[start] <= N[i] + y) {
num ++;
ans[num] = i;
Ans[num] = start;
start ++;
}
}
cout << num << endl;
for(int i = 1; i <= num; i ++) cout << ans[i] << " " << Ans[i] << endl;
return 0;
}
原因:背心使用后没有更新新的查找范围,重复计算了 (b_j) ,而不是从 (b_{j+1}) 开始计算,WA。
原因:背心未被使用时(即某一士兵穿不上所有的背心)没有更新新的查找范围,TLE。
原因:背心使用后,更新新的查找范围多计算了一件,导致从 (b_j+2) 开始查找,而不是从 (b_{j+1}) 开始计算,WA。
原因:(同第一次)
原因:(同第二次)
原因:(本质上和第二次一样,略加了优化,但没有修改到本质,依旧TLE)
原因:二分范围取错,取了士兵的范围进行二分,而不是背心的范围,WA。
文 / WIDA 2021.11.6成文 首发于WIDA个人博客,仅供学习讨论
更新日记: 2021.11.6 成文
以上是脚本宝典为你收集整理的CF161A - Dress'em in Vests!(暴力+贪心/二分/普及级)全部内容,希望文章能够帮你解决CF161A - Dress'em in Vests!(暴力+贪心/二分/普及级)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。