[C++知识库]Codeforces Round #661 (Div. 3) C. Boats Competition

题目链接： https://codeforces.com/problemset/problem/1399/C

题目要求： 要求找出每艘船总重一定时，能凑出的船数最大值(当两人重量之和正好为船总重时才能乘一艘船)。

解题思路： 看题目数据，n很小，直接暴力即可。
一： 根据题目要求，要两个人坐一艘船，又每人体重范围为1~n。则船总重量范围为2 ~2*n。对船的总重进行遍历。
二： 思考可知，必然是体重平均(如最重的和最轻的坐一艘船)的情况能凑成的船数最多。因此对重量排序后采用类似双指针的方法从前后往中间遍历。遍历时有三种情况。(i：船总重)
1：w[l]+w[r]==i，说明l和r刚好能凑一艘船。遍历下一种情况，l++,r- -.
2：w[l]+w[r]<i，说明两人重量比船总重轻，需要重量增加。(因为对重量进行了从小到大的排序，因此要增加重量，l++，左边往右遍历即可)
3：w[l]+w[r]>i，说明两人重量比船总重重。需要减少重量。r- -(原因和2类似)

#include<iostream>
#include<algorithm>
using namespace std;
int w[55];
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> w[i];
		sort(w, w + n);
		int ans = 0;
		for (int i = 2; i <= 2 * n; i++)
		{
			int l = 0, r = n - 1;
			int count = 0;
			while (l < r && l >= 0 && r < n)//船总重为i时，遍历重量求能凑成的船数
			{
				if (w[l] + w[r] == i)//能凑成一船的情况
				{
					count++;
					l++;
					r--;
				}
				else if (w[l] + w[r] < i)//两人重量较船总重轻
					l++;
				else
					r--;
			}
			ans = max(ans, count);//取最大凑成船数
		}
		cout << ans << endl;
	}
	return 0;
}