首页 > 代码库 > qsc oj-17 喵哈哈村的排队
qsc oj-17 喵哈哈村的排队
http://qscoj.cn/problem/17/
喵哈哈村的排队
有一堆喵哈哈村的村民们在排队,他们从队列的尾部开始标号,标号为1的村民站在最后面,标号为n的村民站在队列的最前面,而且每个村民都拥有一个智商值a[i]。
这些村民有时候会觉得不开心,因为他们觉得凭什么一个智商比他低的人,可以站在他的前面!现在对于每个村民,他们都想知道,在他前面,智商比他低,离他最远的距离是多少。
第一行n,表示有n只咸鱼
第二行n个整数,表示每个村民的智商值a[i].
n<=200000 1<=a[i]<=1000000000
对于每个村民,输出智商比他的,且离他最远的距离是多少,如果没有输出-1
复制
6 10 8 5 3 50 45
2 1 0 -1 0 -1
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<stack> 9 #include<cstring> 10 #include<vector> 11 #include<list> 12 #include<set> 13 #include<map> 14 using namespace std; 15 #define ll long long 16 #define pi (4*atan(1.0)) 17 #define eps 1e-14 18 #define bug(x) cout<<"bug"<<x<<endl; 19 const int N=1e5+10,M=1e6+10,inf=2147483647; 20 const ll INF=1e18+10,mod=2147493647; 21 int a[N]; 22 int r[N]; 23 int main() 24 { 25 int n; 26 while(~scanf("%d",&n)) 27 { 28 for(int i=1;i<=n;i++) 29 scanf("%d",&a[i]); 30 r[n]=a[n]; 31 for(int i=n-1;i>=1;i--) 32 r[i]=min(r[i+1],a[i]); 33 for(int i=1;i<=n;i++) 34 { 35 int st=i+1; 36 int en=n,ans=-1; 37 while(st<=en) 38 { 39 int mid=(st+en)>>1; 40 if(a[i]>r[mid]) 41 { 42 st=mid+1; 43 ans=mid; 44 } 45 else 46 en=mid-1; 47 } 48 if(ans==-1) 49 printf("-1"); 50 else 51 printf("%d",ans-i-1); 52 printf("%c",((i==n)?‘\n‘:‘ ‘)); 53 } 54 } 55 return 0; 56 }
qsc oj-17 喵哈哈村的排队
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。