洛谷解题报告

1.题面

2.分析

首先确定这题是贪心。
这道题目的朴素算法呢，就是先找个最重的人揪出来扔船上，然后再找个轻点的人看看能不能和最重的人的一起扔船上。如果能的话，就直接扔进去；否则，就让那个重的自己用一条船就行了。
还有一个稍微好一点的算法，就是找最重的和最轻的做操作。<-解释：把以下应用条中被高亮的部分改成“最轻的”就行了。

这道题目的朴素算法呢，就是先找个最重的人揪出来扔船上，然后再找个轻点的人看看能不能和那个最重的人一起扔船上。如果能的话，就直接扔进去；否则，就让那个大的自己用一条船就行了。

注意，我们只考虑2个人的情况，因为题目要求：租用的独木舟都是一样的，最多乘两人，而且载重有一个限度。（划重点！！！是两人！！！）

3.代码

//
//  main.cpp
//  c++programs
//
//  Created by Theodore H on 2019/5/15.
//  Copyright © 2019 Theodore H. All rights reserved.
//

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <time.h>
#include <climits>
#include <deque>
//以上都是废话
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int a[30005];//每个人重量

int main()
{
    int max_weight, n;//max_weight是船最大载重量
    int sum = 0;//答案
    cin >> max_weight;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }//输入，没加优化，不讲了
    sort(a, a + n);//排个序，递增
    int i = 0, j = n - 1;//两个指针
    while(i <= j)//。。。。。。
    {
        if(a[i] + a[j] <= max_weight)//如果两人(最重和最轻)可以合租一艘船
        {
            i++;//两人以后
            j--;//都不考虑
            sum++;//答案(所需独木舟数量)加一
        }
        else//如果船只能载一个人(最重的那位)
        {
            j--;//以后不考虑这位最重的人
            sum++;//答案(所需独木舟数量)加一
        }
    }
    cout << sum << endl;//输出，不讲了
    return 0;
}

至此，我的题解解题报告写完了。