首页 > 代码库 > 看美女（二）
看美女（二）
看美女（二）
时间限制：1000 ms | 内存限制：65535 KB
难度：2
- 描述
- “排排站，赏美女……”
N个人站成一排。不巧，美女们只在队伍的最左边和最右边，你们可以向左看或者向右看。如果第i个人向左看，当且仅当第i个人的身高h[i]>h[j] （ j=1...i-1） 时，他能看到美女；如果第i个人向右看，当且仅当第i个人的身高h[i]>h[j] （j=i+1..N）时，他能看见美女。已知N个人的身高，为了能让更多的人看到美女，你的任务是找出最好的站队方法，让最多的人能看到美女，输出最多有多少人可以看到美女。
- 输入
- 先输入一个数T 表T组
每组数据： 第一行 N。N<=100 000
第二行 Ｎ个整数， 1<=h<=20000 - 输出
- 输出答案 换行。
- 样例输入
151 4 7 6 2
- 样例输出
5
- 来源
- 原创
- 上传者
- TC_胡仁东
View Code1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 using namespace std;11 int d[100010],tot;12 int main() {13 int kase,i,n,ans,pre;14 scanf("%d",&kase);15 while(kase--) {16 scanf("%d",&n);17 for(i = 0; i < n; i++)18 scanf("%d",d+i);19 sort(d,d+n);20 ans = 1;21 pre = tot = 0;22 for(i = 1; i < n; i++) {23 if(d[i] > d[i-1]) ans++;24 else if(d[i] > pre){25 ans++;26 pre = d[i];27 }28 }29 printf("%d\n",ans);30 }31 return 0;32 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。