文档章节

7_12_2013 E: Hard problem

電泡泡
 電泡泡
发布于 2013/07/19 18:07
字数 509
阅读 6
收藏 0

Problem E: Hard problem

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 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;
}


© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 23
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
Rsyslog 7.4.6 发布,多线程 syslogd 版本

日志系统Rsyslog 7.4.6发布.2013-10-31 上个版本是2013-10-22的7.4.5。这是一个Bug修正版。修正了一些Bug 其他产品系列是6.6.0 6.4.2 5.10.1 开发版7.5.6,现在Rsyslogd基本是syslogd的标准了...

fei
2013/11/01
740
1
262. Trips and Users

Description Difficulty: Hard Tag: Sql The Trips table holds all taxi trips. Each trip has a unique Id, while ClientId and DriverId are both foreign keys to the UsersId at the Us......

52iSilence7
01/04
0
0
《专家系统破解篇 六、IL代码破解》之 加载重述

![在此输入图片描述][1] 通过加载,得到 C类1000个, E类 多少条规则个。 C类中的IP指向规则, O有四个, 第O为的事实 对应在4个规则中做条件。 至于条件的正反与规则的信息, 根据其 IP指向...

马知常
2013/06/25
0
0
java servic wrapper jvm启动五遍后就停止

STATUS | wrapper | 2013/04/03 12:01:35 | Launching a JVM... INFO | jvm 1 | 2013/04/03 12:01:36 | there are all ok ERROR | wrapper | 2013/04/03 12:01:36 | JVM exited while loadin......

这个世界不真实
2013/04/03
1K
1
Rsyslog 7.4.5 发布,多线程 syslogd 版本

日志系统Rsyslog 7.4.5发布.2013-10-22 上个版本是2013-09-04的7.4.4。这是一个Bug修正版。修正了一些Bug 其他产品系列是6.6.0 6.4.2 5.10.1 开发版7.5.5,现在Rsyslogd基本是syslogd的标准了...

fei
2013/10/23
895
2

没有更多内容

加载失败,请刷新页面

加载更多

rabbitmq安装教程

RabbitMQ有Windows与Linux版本的,这里先写Windows版本的安装。 以前安装软件总是在百度上找某某安装教程,结果能按照教程安装好的软件真的不多。想起先前以为大牛说的一句话,去官网按照官网...

em_aaron
今天
6
0
Android 贝塞尔曲线实践——波浪式运动

一、波浪效果如下 贝塞尔曲线自定义波浪效果的案例很多,同样方法也很简单,大多数和本案例一样使用二次贝塞尔曲线实现,同样还有一种是PathMeasure的方式,这里我们后续补充,先来看贝塞尔曲...

IamOkay
今天
2
0
Nmap之防火墙/IDS逃逸

选项 解释 -f 报文分段 --mtu 指定偏移大小 -D IP欺骗 -sI 原地址欺骗 --source-port 源端口欺骗 --data-length 指定发包长度 --randomize-hosts 目标主机随机排序 --spoof-mac Mac地址欺骗 ...

Frost729
今天
2
0
带你搭一个SpringBoot+SpringData JPA的环境

不知道大家对SpringBoot和Spring Data JPA了解多少,如果你已经学过Spring和Hibernate的话,那么SpringBoot和SpringData JPA可以分分钟上手的。 其实我在学完SpringBoot和SpringData JPA了之...

java菜分享
今天
7
0
Chocolatey 在Window搭建一个开发环境

在看了(利用 Chocolatey 快速在 Windows 下搭建一个开发环境)后,准备从零开始 一、准备工作 1、用管理员权限启动:powershell,执行错误请参考(PowerShell因为在此系统中禁止执行脚本的解...

近在咫尺远在天涯
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部