模考：百万富翁的第二次实验 题解

经验分享区
1

百万富翁的第二次实验

题面

马克吐温有一本非常著名的小说《百万英镑》，这本小说中主角最后归还了百万英镑给两位富翁。但结果就是两位富翁依然有无穷的问题需要进行社会实验，于是，他们打算进行第二次社会实验。那就是不同财富值的人在一场舞会上会发生什么事情。为了满足自己的好奇，百万富翁们邀请了全伦敦所有人来自己的舞会。舞会开始后他们就后悔了，因为来的人太多了，而且很多人的财富都相同，统计起来太费事了。所以百万富翁们找到你，希望你根据来舞会的时间，找出在一段时间内，来舞会的所有人财富值都互不相同的人数。

输入格式
第一行输入一个n表示有n个人参与舞会。
按照时间顺序输入n个人的财富值。

输出格式
输出在一段时间内参加舞会的所有人财富值都互不相同的人数的最大值。

数据范围
每个人的财富值不超过100000000000
0 <= n <= 1000000

题解

  1. 用 map 维护出一个值最后出现的位置。
    m[now] = i + 1;
  2. 在遇到重复时，更新合法长度。
    if (m[now] != 0)
    len = min(i - m[now] + 1, len);
    （为什么要取min，样例1 2 3 2 1）
  3. 在枚举的过程中，ans = max(len)
    ans = max(ans, len);
    最后输出：cout << ans
    注意：map 的下标要开 long long
3 个赞