首页 > 代码库 > gym-101343H-Give Me This Pizza
gym-101343H-Give Me This Pizza
1 /* 2 对于数组的每个元素,找到它右边的第一个比它大的元素 3 根据数组元素内容建立索引,有序记录a的每个值的所有出现的位置,然后对于每个a, 4 遍历所有大于a的可能的值,每个值用二分搜索找到当前位置右边的最小的出现位置, 5 (直接遍历会超时) 6 然后这些位置中取最小值即为结果所在的位置。 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 const int inf=0x3f3f3f3f; 11 int n; 12 int a[100005]; 13 int f[55][100005]; 14 int len[55]; 15 int main() 16 { 17 cin>>n; 18 memset(len,0,sizeof(len)); 19 for(int i=1;i<=n;i++) 20 { 21 cin>>a[i]; 22 f[a[i]][len[a[i]]]=i; 23 len[a[i]]++; 24 } 25 for(int i=1;i<=n;i++) 26 { 27 int num=a[i]; 28 int wz=inf; 29 for(int j=num+1;j<=50;j++) 30 { 31 // for(int l=0;k<len[j];l++) 32 // { 33 // if(f[j][l]>i&&f[j][l]<wz) 34 // wz=f[j][l]; 35 // } 36 int l=0,r=len[j]-1; 37 while(l<r) 38 { 39 int mid=(l+r)/2; 40 if(f[j][mid]>i) 41 r=mid; 42 else 43 l=mid+1; 44 } 45 if(f[j][r]>i) 46 if(wz>f[j][r]) 47 wz=f[j][r]; 48 } 49 if(wz==inf) 50 cout<<-1<<‘ ‘; 51 else 52 cout<<a[wz]<<‘ ‘; 53 } 54 cout<<endl; 55 }
gym-101343H-Give Me This Pizza
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。