## 题目描述
n个人,已知每个人体重,独木舟承重固定,每只独木舟最多坐两个人,可以坐一个人或者两个人。显然要求总重量不超过独木舟承重,假设每个人体重也不超过独木舟承重,问最少需要几只独木舟?
**输入**
第一行包含两个正整数n (0<n<=10000)和m (0<m<=2000000000),表示人数和独木舟的承重。 接下来n行,每行一个正整数,表示每个人的体重。体重不超过1000000000,并且每个人的体重不超过m。
**输出**
一行一个整数表示最少需要的独木舟数。
## 题目分析
一个显然的策略是按照人的体重排序。
极端化贪心策略,最重的人要上船——如果最重的人和最轻的人体重总和不超过船的承重,则他们两个占用一条船。否则(因为假设最重的人的体重也不超过船的承重了),最重的人单独占一条船。转变为(n – 1)或者(n – 2)的问题了。
关键在于这种贪心策略是正确的。我们可以证明,最优解也可以变为这种策略。
(1) 假设最重的人和最轻的人的体重和超过了船的承重,那么最优解中,显然也是最重的人单独占一条船,所以这种情况下最优解和贪心策略是相同的。
(2) 假设最重的人和最轻的人的体重和没超过船的承重。 (2.1)如果最优解中,最重的人单独占用一条船,则可以把最轻的人也放上去,这样最优解用的船数不增加。如果最轻的人占用一条船,同样我们可以把最重的人放上去,最优解船数不增。
(2.2) 如果最优解中最重的人x和x’占用一只船(x, x’),而最轻的人y和y’占用一只船(y, y’) 我们换成(x, y) (x’,y’)
(x, y)显然没超过船的承重——因为我们假设就是如此。关键看(x’, y’)。
x’ + y’<= x’ + x 因为(x’, x)没超重,所以(x’,y’)也合法。所以换一下,最优解船数也不增。这样我们就证明了如果可能把最重的人和最轻的人放在一条船上,不会影响最优解。
反复应用这个策略,就可以把n降低为(n – 1)或者(n – 2)个人的规模,从而解决这个问题。
## Code
~~~
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x7f7f7f7f
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
int a[maxn];
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
int i,j,sum=0;
cin>>n>>m;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
i=0;
j=n-1;
//保证数据没有重叠
while(i<=j)
{
//i=j,即:最后剩下一个人,因为其他人都上船了,所以不管他有没有超重,只能自己在一个船上
if(i==j)
{
sum++;
break;
}
if(a[i]+a[j]<=m)
{
sum++;
i++;
j--;
}
//有一个人偏重,让这个人自己在一个船上,然后保持体重轻的(假设是A)不上船,找到一个能和他待在一个船上的人
else
{
//找一个体重稍微轻点的去和A放在一起,重复以上操作
j--;
//重的那个人自己在一个船上
sum++;
}
}
cout<<sum<<endl;
return 0;
}
~~~
对应题目:[51Nod 1432](https://www.51nod.com/Challenge/Problem.html#!#problemId=1432)
- 简介
- 零基础快速入门ACM
- C语言快速入门
- C语言快速入门
- C/C++基础
- 输入输出
- 数组和字符串
- 数组
- 字符数组
- 函数和递归
- C++标准容器库(STL)
- Vector
- Map
- Set
- String
- Stack
- Queue
- Priority_queue
- 贪心
- 硬币问题
- 区间调度问题
- 字典序最小问题
- 独木舟问题
- 搜索
- DFS
- BFS
- 剪枝
- 记忆化搜索
- 常用技巧
- 倍增
- 高精度
- 大数加法
- 大数减法
- 大数乘法
- 大数除法
- 大数阶乘
- 输入挂
- 前缀和
- 二分
- 本地预处理
- 尺取
- 枚举
- 坐标离散化
- 分治
- 数列分治
- 树上分治
- 平面分治
- 计算几何
- 凸包
- 点积
- 叉积
- 线段关系
- 皮克定理
- 最近点对
- 数据结构
- 线段树
- 树状数组
- 并查集
- 动态规划
- 基础知识
- 信息学竞赛中的动态规划
- 动态规划初步
- 最长上升子序列(LIS)
- 最长公共子序列(LCS)
- 最大子段和
- 背包问题
- 部分背包
- 0 1 背包
- 完全背包
- 多重背包
- 背包的可行性问题
- 线性DP
- 树形DP
- 区间DP
- 数位DP
- 动态规划优化
- 字符串
- KMP算法
- 拓展KMP
- 字符串Hash
- Manacher算法
- 后缀数组
- Trie树
- 博弈论
- Nim博弈
- Bash博弈
- 斐波那契博弈
- 威佐夫博弈
- SG函数
- 数论
- 整数研究
- 素数判断
- 素数筛选
- 快速幂
- 算数基本定理
- 最大公约数(Gcd)
- 费马小定理
- 扩展欧几里得
- 逆元
- 同余定理
- 组合数学
- 容斥原理
- 抽屉原理
- 卢卡斯(Lucas)
- 卡特兰(Catalan)
- 著名函数
- 欧拉函数
- 莫比乌斯函数
- 线性代数
- 矩阵运算
- 矩阵快速幂
- 图论
- 存图方法
- 邻接矩阵
- 邻接表
- Vector存图
- 链式前向星
- 图的遍历
- 拓扑排序
- 最短路
- Dijkstra算法
- SPFA算法
- Floyed 算法
- 最小生成树
- Prim算法
- Kruskal算法
- 最近公共祖先 (LCA)
- 二分图匹配
- 网络流
- 其他
- 莫队