2019独角兽企业重金招聘Python工程师标准>>> 
Problem E: Hard problem
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 63 Solved: 21
[ Submit][ Status][ Web Board]
Description
The cat gets N mice from dreamone, and she can choose K mice from them as the order which is listed from
left to right for dinner. But there is a limitation that the second mouse is no bigger than the first one, the third
one is no bigger than the second one….the Kth one is no bigger than the (K-1) th one. Actually, there is always
not a single method to choose the K mice from the N mice as the way described above; we can assume there
is M ways. This time, the cat of dreamone’s has thought another hard problem:
For each way, there is always a value for the Kth mouse. She wants to know the biggest value for the Kth
mouse of all the M ways. Can you get it? Of course, not all of you have understood the idea, so there is an
example blew:
We can assume N=4, K=2.
The N (N=4) numbers represented the N mice are given blew from left to right:
4 6 5 4
According to the rules above, we can get four ways for choosing K mice, such as:
4 4; 6 5; 6 4; 5 4
So the answer is 5.because the value 5 is the biggest one of the four ways for the Kth number.
If the cat can not solve the problem as quickly as she can, she will feel very boring, so she turns to you, a
topcoder of SWUST, for help. Can you help her?
Input
The first line of input will be a positive integer indicating how many test cases will be included (T). Each of
the next T cases will contain two parts:
The first part: two integer N, K (1<=N<=10000, 1<=K<=10)
The second part: N numbers (which is no larger than 1000000) represented the N mice from left to right.
Output
For each test, you should output the biggest value for the Kth numbers of all the manners. If you can not find
any way to choose the Kth mouse, just output “OH, NO” instead.
Sample Input
2 4 2 4 6 5 4 4 2 1 2 3 4
Sample Output
5 OH,NO
#include <iostream>
#include <stdio.h>
using namespace std;
int
main()
{
int tu, n, k;
int s[11], num[10010];
while(tu--){
for(int i=0; i<=10; i++)
s[i]=0;
cin>>n>>k;
cin>>s[0];
s[0]=num[0];
for(int i=1; i<n; i++){
cin>>num[i];
for(int j=0; j<=10; j++){
if(num[j]>0){
if(num[i]<s[j]){
s[j]=num[i];
}
else{
s[j+1]=num[i];
break;
}
}
}
}
cout<<endl<<"****";
for(int i=0; i<10; i++){
cout<<s[i]<<" ";
}
cout<<endl;
if(s[k]==0){
cout<<"OH,NO"<<endl;
}
else{
cout<<s[k]<<endl;
}
}
return 0;
}