河南企业网站优化外包,php网站开发电子书,杭州公司的网站建设公司,网络服务遇到问题请稍后再试吧世界警察小码哥来谈判了#xff0c;恐怖分子在银行挟持了 n 个人质#xff0c;每个人质都所属一个国家#xff0c;第 i 个人质所属的国家为 ci#xff0c;人质排成了一排#xff0c;位置都是固定的。经过商讨#xff0c;恐怖分子允许小码哥可以带走任意一段连续区间内的…世界警察小码哥来谈判了恐怖分子在银行挟持了 n 个人质每个人质都所属一个国家第 i 个人质所属的国家为 ci人质排成了一排位置都是固定的。经过商讨恐怖分子允许小码哥可以带走任意一段连续区间内的人质。但是上级要求小码哥最好每个国家的人质都带回来一个不希望人质中有重复的国家。请问小码哥最多可以带出来多少人质。
格式
输入格式
第一行一个正整数 n表示共有 n 个人质 第二行共有 n 个正整数第 i 个正整数表示第 i 个人质的所属国家 ci。
输出格式
一个整数表示小码哥最多可以带出来的人质数。
样例 1
输入
5
1 1 2 3 4输出
4备注
其中1≤n≤10^60≤ci≤10^9。
思路双指针
代码1不严谨代码这里的数据ci并没有取到10^9
#include bits/stdc.h
using namespace std;
const int N 1000005;
int n;
int c[N];
int st[N];
int main()
{cin n;for (int i 0; i n; i){cin c[i];}int res 0;for (int i 0, j 0; i n; i){st[c[i]];while (j i st[c[i]] 1){st[c[j]]--;j;}res max(res, i - j 1);}cout res;return 0;
} ps这题数据好弱
代码2用map存ci和对应的次数
#include bits/stdc.h
using namespace std;
const int N 1000005;
int n;
int c[N];
mapint, int mp;
int main()
{cin n;for (int i 0; i n; i){cin c[i];}int res 0;for (int i 0, j 0; i n; i){mp[c[i]];while (j i mp[c[i]] 1){mp[c[j]]--;j;}res max(res, i - j 1);}cout res;return 0;
}
