游船(upc)c++

游船(upc)c++

题目描述

有n个学生去划船，第i个学生的体重是w[i]。湖面上有好多船，每艘船的安全载重都是S。船的载重量由管理员统一设置。每艘船必须坐两个学生，而且这两个学生的体重的和必须等于S，这样的船才能“平衡”。现在的问题是：管理员应该如何设置S，才能使得有最多的船能够“平衡”。注意：一个学生最多只能乘一艘船。

输入

 第一行，一个整数n。1<=n<=50。
 第二行，n个整数，第i个整数是w[i]，1<=w[i]<=n。

输出

一个整数，表示最多有多少艘船可以平衡。

样例输入 Copy

【样例1】
5
1  2  3  4  5
【样例2】
8
6 6 6 6 6 6 8 8
【样例3】
8
1 2 2 1 2 1 1 2
【样例4】
3
1 3 3
【样例5】
6
1 1 3 4 2 2

样例输出 Copy

【样例1】
2
【样例2】
3
【样例3】
4
【样例4】
1
【样例5】
2

思路：

        首先将输入的数存到数组里，因为题目S不确定，我们需要找到这S，使得最多的船平衡，因此需要对S最外层做一个循环遍历，再到里面遍历数组找到相加等于S的情况，再将这个S下平衡呢的次数与最多次数比较，存下最大值，最后输出即可

代码：

        #include<bits/stdc++.h>
using namespace std;
int a[55],b[55];
int main(){
    int n;
    cin>>n;
    int i;
    for (i=0;i<n;i++){
        cin>>a[i];
        b[i]=a[i];  //为了后面的操作不影响原来输入的值 
    }
    int s,j,ans=0,l=0;
    for (s=2;s<=100;s++){   //最外层循环 
        for (i=0;i<n;i++){
            for (j=i+1;j<=n;j++){
                if (b[i]+b[j]==s){
                    ans++;
                    b[i]=1000;   //避免出现重复的数，而导致这个位置的数被重复用 
                    b[j]=1000;
                }
            }
        }
        l=max(ans,l);
        ans=0;
        for (i=0;i<n;i++){
            b[i]=a[i]; 
        }    
    }
    cout<<l;
}