admin管理员组文章数量:1530041
Boats Competition原题
题面翻译
有 n n n 个人要参与两人一组的划船比赛,第 i i i 个人的质量为 w i w_i wi 。
作为比赛的组织者,你希望通过这样的方式使得比赛公平:每队的两位选手的质量和都相等。
即,如果有 k k k 组,第 i i i 组的两位选手的质量分别为 ( a i , b i ) (a_i,b_i) (ai,bi) ,那么需要满足以下条件:
a 1 + b 1 = a 2 + b 2 = . . . = a k + b k = s a_1+b_1=a_2+b_2=...=a_k+b_k=s a1+b1=a2+b2=...=ak+bk=s
你需要找到这样的一个 s s s ,使得队伍数( k k k )尽可能多。
样例 #1
样例输入 #1
5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 1 2 1 1 2
3
1 3 3
6
1 1 3 4 2 2
样例输出 #1
2
3
4
1
2
解题思路
- 思路;这是一个双指针的题目,数据范围很小,因此可以枚举每一个质量,然后遍历数组寻找两两相加等于这个质量的最大对数,然后再取最大对数即可。
代码
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,w[100],ans=0,num[110];
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i];
}
sort(w+1,w+n+1); //把质量排序
for(int k=1;k<=110;k++){//数据范围比较小,因此可以枚举每一种可能质量
//都个数
int l=1,r=n;//两个指针
int cnt=0;//记录一个k对应的对数
while(1){
while(w[l]+w[r]==k && l<r){
l++;
r--;
cnt++;
}
while(w[l]+w[r]<k && l<r){//因为序列单调,所以 小于k那就左指针
//右移
l++;
}
while(w[l]+w[r]>k && r>l){//与上面相反 右指针左移
r--;
}
if(l>=r){//两个指针相遇那么就结束循环
break;
}
}
ans=max(ans,cnt);//取最大的对数
}
cout<<ans<<endl;
}
return 0;
}
本文标签: 指针Boatscompetition
版权声明:本文标题:Boats Competition(双指针) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1726693002a1080906.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论