Odd Gnome【枚举】
问题 I: Odd Gnome
时间限制: 1 Sec 内存限制: 128 MB
提交: 234 解决: 144
[提交] [状态] [命题人:admin]
题目描述
According to the legend of Wizardry and Witchcraft, gnomes live in burrows underground, known as gnome holes. There they dig
up and eat the roots of plants, creating little heaps of earth around gardens, causing considerable damage to them.
Mrs. W, very annoyed by the damage, has to regularly de-gnome her garden by throwing the gnomes over the fence. It is a lot of work to throw them one by one because there are so many. Fortunately, the species is so devoted to their kings that each group always follows its king no matter what. In other words, if she were to throw just the king over the fence, all the other gnomes in that group would leave.
So how does Mrs. W identify the king in a group of gnomes? She knows that gnomes travel in a certain order, and the king, being special, is always the only gnome who does not follow that order.
Here are some helpful tips about gnome groups:
• There is exactly one king in a group.
• Except for the king, gnomes arrange themselves in strictly increasing ID order.
• The king is always the only gnome out of that order.
• The king is never the first nor the last in the group, because kings like to hide themselves.
Help Mrs. W by finding all the kings!
输入
The input starts with an integer n, where 1 ≤ n ≤ 100, representing the number of gnome groups. Each of the n following lines contains one group of gnomes, starting with an integer g, where 3 ≤ g ≤ 1 000,representing the number of gnomes in that group. Following on the same line are g space-separated integers, representing the gnome ordering. Within each group all the integers (including the king) are unique and in the range [0, 10 000]. Excluding the king, each integer is exactly one more than the integer preceding it.
输出
For each group, output the king’s position in the group (where the first gnome in line is number one).
样例输入
3 7 1 2 3 4 8 5 6 5 3 4 5 2 6 4 10 20 11 12
样例输出
5 4 2 题意: 给出一个序列,序列中有一个King,除了King其他都是递增的,找出King的位置 King不会在第一个和最后一个的位置 那很明显就是枚举2--n-1的位置,找出满足以下两个条件的位置 1.a[i-1] < a[i+1] 2.a[i] > a[i + 1] && a[i] > a[i - 1] 或者 a[i - 1] < a[i + 1]&& a[i] < a[i + 1]
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
const int maxn = 1000005;
int a[maxn];
int n;
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 2; i < n; i++)
if ((a[i] > a[i + 1] && a[i] > a[i - 1] && a[i - 1] < a[i + 1] )
||( a[i - 1] < a[i + 1]&& a[i] < a[i + 1] && a[i] < a[i - 1])) {
printf("%d\n", i);
break;
}
}
return 0;
}
最新文章
- Code Snippets 代码片段
- Sublime 3 如何设置xftp 排除文件夹“bower_components”,“node_modules”
- 播放wav聲音格式
- UML建模——概述
- 基于定位下拉框或者需要点击link才显示的下拉框,二次定位与多次定位实现的实际效果区别
- iPhone safari中Document事件不触发的解决方案 [冒泡]
- JEECG中出现Java.sql.SQLException: Value &#39;xxxx&#39; can not be represented as java.sql.Timestamp的解决办法
- 基于.NET的APP开发和Windows开发,异步回调差别
- 用switch组件控制一个元素的显示和隐藏状态
- Java:ConcurrentHashMap的锁分段技术
- Android——MaterialDesign之二DrawerLayout
- MT【301】值域宽度
- MySQL----数据库练习
- Linux中常用的50个命令
- Java用JSONObject-lib来解析json串
- web.xml不同版本的头
- Spring AOP 不同配置方式产生的冲突问题
- Codeforces Round #385 (Div. 2)A B C 模拟 水 并查集
- Ubuntu下安装配置java及环境变量
- <;!--注释-->;和<;%--注释--%>;有什么区别