首页 > 试题广场 >

物流中心包裹分拣

[编程题]物流中心包裹分拣
  • 热度指数:24 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 512M,其他语言1024M
  • 算法知识视频讲解
你是一家大型物流中心的分拣主管。
一条传送带上源源不断地送来包裹,每个包裹上都标有一个目的地编号。
这一连串的包裹可以看作一个整数数组 A

你的任务是将这一整条传送带上的包裹,划分成最多数量的连续“批次”。
每一个批次会被送到一个独立的机器人处进行整理,机器人会将该批次内的包裹按照目的地编号从小到大排序。
所有批次都整理完毕后,再按照原先批次的先后顺序重新拼接起来。

你需要设计一种划分方案,使得最终拼接好的包裹序列,与将所有包裹一次性进行全局排序的结果完全一致。

请问,你最多能将这些包裹划分成多少个批次?

输入描述:
输入为一行,包含多个由空格隔开的正整数,代表传送带上每个包裹的目的地编号。

数据范围 :
包裹总数 N 的范围为 [1, 500]
每个包裹的目的地编号 A_i 都是一个正整数。


输出描述:
输出一个整数,代表最多可以划分的批次数。
示例1

输入

2 1 3 4 4 5

输出

5
示例2

输入

5 4 3 2 1

输出

1

备注:
本题由牛友@Charles 整理上传

这道题你会答吗?花几分钟告诉大家答案吧!