admin管理员组

文章数量:1530013

Codeforces Round #661 (Div. 3)   参与排名人数12987

[codeforces 1399C]   Boats Competition   桶排序+从总重量出发统计队数+注意边界处理

总目录详见https://blog.csdn/mrcrack/article/details/103564004

在线测评地址https://codeforces/contest/1399/problem/C

ProblemLangVerdictTimeMemory
C - Boats Competition GNU C++17Accepted62 ms3900 KB

题目大意：给出n个人的重量，要求两个人组成一队，组成的队伍中，每队的重量都必须相同，问，最多能组成的队数。

基本思路：桶排序+从总重量出发统计队数+注意边界处理.特别注意边界处理(详见代码)0<s-a[j]关键，不能省，保证b[s-a[j]]数组元素位置不会是负数,少了这处判断，会造成Wrong answer on test 2。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[55],cnt[55],b[55];
int main(){
	int t,n,i,tot,s,mx,j;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=1;i<=50;i++)cnt[i]=0;
		for(i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;//桶排序
		mx=0;
		for(s=n*2;s>=1;s--){//从总重量出发，进行枚举
			tot=0;
			for(j=1;j<=50;j++)b[j]=cnt[j];
			for(j=1;j<=n;j++)//一个人重量a[j]，另一个人重量s-a[j]
				if(0<s-a[j]&&s-a[j]<=n&&b[s-a[j]]>0){//0<s-a[j]关键，不能省，保证b[s-a[j]]数组元素位置不会是负数,少了这处判断，会造成Wrong answer on test 2 
					b[a[j]]--,b[s-a[j]]--;
					if(b[a[j]]>=0&&b[s-a[j]]>=0)tot++;//可能出现a[j]==s-a[j]的情况，故需作此判断
				}
			mx=max(mx,tot);//找最大队的数量
		}
		printf("%d\n",mx);
	}
	return 0;
}

 

本文标签： 边界总重量codeforcescompetitionBoats

版权声明：本文标题：[codeforces 1399C] Boats Competition 桶排序+从总重量出发统计队数+注意边界处理 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1726694318a1081033.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。