Title description

Xiao Fei recently became obsessed with a game called PlayerUnknown’s Battlegrounds. But his technique is not good, suppose his combat power is x. However, his combat effectiveness is determined by his mood, and it is different every day. There is a group of (1≤n≤100000) friends who are also playing PUBG, and they also have combat effectiveness. Xiao Fei wanted to find someone better than himself to play and improve his combat effectiveness, such as: Xiao Ye, Xiao Zu, Xiao Ming, etc.

Xiao Fei played for a total of m days, assuming that the combat effectiveness of other people remains unchanged. Question: How many people can Xiao Fei find better than himself every day.

Input and output format

Input format

On the first line, enter an n, which means there are n friends; (1≤ n≤100000)

Enter the combat power of n friends in the second line; each friend’s combat power does not exceed long int (pre-ordered);

Enter an m in the third line, which means There are m days; (1≤m≤100000)

The next m lines indicate Xiao Fei’s daily combat effectiveness; (Xiao Fei’s combat effectiveness does not exceed the range of int).

Output format

There are m lines in total, and the number of people Xiao Fei finds every day in each line.

Input and output sample

< strong>Sample input

5

1 1 3 5 5

3

0

< p>2

5

Output sample

5

3

0

Question solution

Binary search template Question, violence is enough.

#include

using namespace std;

int n,m,a[100005], k[100005],mid;

int main()

{

 cin>>n;

 for(int i=1;i<=n;i++)

 {

 cin>>a[i];

}

 cin>>m;

 for(int i=1;i<=m;i++)

 {

 cin>>k[i];

}

 for(int i=1;i<=m;i++)

 {

 for(int low=0,high=n+1;;)

 {

 mid=(low+high)/2;

 if(mid==low||mid==high)

 {

 cout<mid;

 break;

}

 else if(a[mid]<=< span style="color: #000000;">k[i])

 {

 if(a[mid+1]>k[i])

 {

 cout<mid;

 break;

}

 else

 {

 low=mid;

}

}

 else

 {

 if(a[mid-1]<= k[i])

 {

 cout<1;

 break;

}

 else

 {

 high=mid;

}

}

}

 if(iendl;

}

 return 0;

} 

Reference program

Sample output

5

3

0

p>

Question solution

Find the template question in two ways, just use violence.

#include

using namespace std;

int n,m,a[100005], k[100005],mid;

int main()

{

 cin>>n;

 for(int i=1;i<=n;i++)

 {

 cin>>a[i];

}

 cin>>m;

 for(int i=1;i<=m;i++)

 {

 cin>>k[i];

}

 for(int i=1;i<=m;i++)

 {

 for(int low=0,high=n+1;;)

 {

 mid=(low+high)/2;

 if(mid==low||mid==high)

 {

 cout<mid;

 break;

}

 else if(a[mid]<=< span style="color: #000000;">k[i])

 {

 if(a[mid+1]>k[i])

 {

 cout<mid;

 break;

}

 else

 {

 low=mid;

}

}

 else

 {

 if(a[mid-1]<= k[i])

 {

 cout<1;

 break;

}

 else

 {

 high=mid;

}

}

}

 if(iendl;

}

 return 0;

} 

Reference program

< strong>Sample input

5

1 1 3 5 5

3

0

< p>2

5

Output sample

5

3

0

Question solution

Find the template question in two ways, just use violence.

#include

using namespace std;

int n,m,a[100005], k[100005],mid;

int main()

{

 cin>>n;

 for(int i=1;i<=n;i++)

 {

 cin>>a[i];

}

 cin>>m;

 for(int i=1;i<=m;i++)

 {

 cin>>k[i];

}

 for(int i=1;i<=m;i++)

 {

 for(int low=0,high=n+1;;)

 {

 mid=(low+high)/2;

 if(mid==low||mid==high)

 {

 cout<mid;

 break;

}

 else if(a[mid]<=< span style="color: #000000;">k[i])

 {

 if(a[mid+1]>k[i])

 {

 cout<mid;

 break;

}

 else

 {

 low=mid;

}

}

 else

 {

 if(a[mid-1]<= k[i])

 {

 cout<1;

 break;

}

 else

 {

 high=mid;

}

}

}

 if(iendl;

}

 return 0;

} 

reference program

#include

using namespace std;

int n,m,a[100005], k[100005],mid;

int main()

{

 cin>>n;

 for(int i=1;i<=n;i++)

 {

 cin>>a[i];

}

 cin>>m;

 for(int i=1;i<=m;i++)

 {

 cin>>k[i];

}

 for(int i=1;i<=m;i++)

 {

 for(int low=0,high=n+1;;)

 {

 mid=(low+high)/2;

 if(mid==low||mid==high)

 {

 cout<mid;

 break;

}

 else if(a[mid]<=< span style="color: #000000;">k[i])

 {

 if(a[mid+1]>k[i])

 {

 cout<mid;

 break;

}

 else

 {

 low=mid;

}

}

 else

 {

 if(a[mid-1]<= k[i])

 {

 cout<1;

 break;

}

 else

 {

 high=mid;

}

}

}

 if(iendl;

}

 return 0;

} 

reference program

#include

using namespace std;

int n,m,a[100005], k[100005],mid;

int main()

{

 cin>>n;

 for(int i=1;i<=n;i++)

 {

 cin>>a[i];

}

 cin>>m;

 for(int i=1;i<=m;i++)

 {

 cin>>k[i];

}

 for(int i=1;i<=m;i++)

 {

 for(int low=0,high=n+1;;)

 {

 mid=(low+high)/2;

 if(mid==low||mid==high)

 {

 cout<mid;

 break;

}

 else if(a[mid]<=< span style="color: #000000;">k[i])

 {

 if(a[mid+1]>k[i])

 {

 cout<mid;

 break;

}

 else

 {

 low=mid;

}

}

 else

 {

 if(a[mid-1]<= k[i])

 {

 cout<1;

 break;

}

 else

 {

 high=mid;

}

}

}

 if(iendl;

}

 return 0;

}