| 例2.9 | 找x | （九度教程第17题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
题目描述：
输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。
输入：
测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。
输出：
对于每组输入,请输出结果。
样例输入：
2
1 3
0
样例输出：
-1
#include <stdio.h>
int main () {
int buf[200];
int n;
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%d",&buf[i]);
} //输入数据
int x , ans = -1; //初始化答案为-1，以期在找不到答案时能正确的输出-1
scanf ("%d",&x);
for (int i = 0;i < n;i ++) { //依次遍历数组元素
if (x == buf[i]) {//目标数字与数组元素依次比较
ans = i;
break; //找到答案后跳出循环
}
}
printf("%d\n",ans);
}
return 0;
}
| 例2.10 | 查找学生信息 | （九度教程第18题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
题目描述：
输入N个学生的信息，然后进行查询。
输入：
输入的第一行为N，即学生的个数(N<=1000)
接下来的N行包括N个学生的信息，信息格式如下：
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下：
02
03
01
04
输出：
输出M行，每行包括一个对应于查询的学生的信息。
如果没有对应的学生信息，则输出“No Answer!”
样例输入：
4
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
5
02
03
01
04
03
样例输出：
02 刘唐 男 23
03 张军 男 19
01 李江 男 21
04 王娜 女 19
03 张军 男 19
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Student{ //用于表示学生个体的结构体
char no[100]; //学号
char name[100]; //姓名
int age; //年龄
char sex[5]; //性别
bool operator < (const Student & A) const { //重载小于运算符使其能使用sort函数排序
return strcmp(no,A.no) < 0;
}
}buf[1000];
int main () {
int n;
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%s%s%s%d",buf[i].no,buf[i].name,buf[i].sex,&buf[i].age);
} //输入
sort(buf,buf + n); //对数组排序使其按照学号升序排列
int t;
scanf ("%d",&t); //有t组询问
while (t -- != 0) { //while循环保证查询次数为t
int ans = -1; //目标元素下标,初始化为-1
char x[30];
scanf ("%s",x); //待查找学号
int top = n - 1,base = 0; //初试时，开始下标0,结束下标n-1,查找子集为整个数组
while(top >= base) { //当查找子集不为空集时重复二分查找
int mid = (top + base) / 2; //计算中间点下标
int tmp = strcmp(buf[mid].no,x); //比较中间点学号与目标学号
if (tmp == 0) {
ans = mid;
break; //若相等,则查找完成跳出二分查找
}
else if (tmp > 0) top = mid - 1; // 若大于,则结束下标变为中间点 前一个点下标
else base = mid + 1; //若小于,则开始点下标变为中间点后一个点坐标
}
if (ans == -1) { //若查找失败
printf("No Answer!\n");
}
else printf("%s %s %s %d\n",buf[ans].no,buf[ans].name,buf[ans].sex,buf[ans].age); //若查找成功
}
}
return 0;
}
| 题目1126 | 打印极值点下标 | （九度教程第19题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
#include <stdio.h>
int main(){
int n;
while(scanf("%d",&n) != EOF){
while(n--){
int k, flag = 0;
scanf("%d",&k);
int a[k];
for(int i=0; i<k; i++)scanf("%d",&a[i]);
if(a[0]!=a[1]){flag=1;printf("0");}
for(int i=1; i<k-1; i++){
if((a[i]<a[i-1]&&a[i]<a[i+1])||(a[i]>a[i-1]&&a[i]>a[i+1])){
if(flag==1){printf(" %d",i);}
else {printf("%d",i);flag=1;}
}
}
if(a[k-1]!=a[k-2]){if(flag=1)printf(" %d",k-1);else printf("%d",k-1);}
printf("\n");
}
}
}
//最后一个极值之后不需要输出空格
| 题目1173 | 查找 | （九度教程第20题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
题目描述：
输入数组长度 n 输入数组 a[1...n] 输入查找个数m 输入查找数字b[1...m] 输出 YES or NO 查找有则YES 否则NO 。
输入：
输入有多组数据。每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m<=n<=100）。
输出：
如果在n个数组中输出YES否则输出NO。
样例输入：
5
1 5 2 4 3
3
2 5 6
样例输出：
YES
YES
NO
#include <iostream>
#include <algorithm>
using namespace std;
int N; //数组长度
int main()
{
while(cin>>N!=0)
{
int a[100]={0};
for(int i=1;i<=N;i++)
{
cin>>a[i]; //输入数组
}
sort(a+1,a+N+1);
int m;
cin>>m; //有m组查找
while(m--!=0)
{
int t;
cin>>t; //输入查找数字
int base=1;
int top=N;//初试时，开始下标1,结束下标N
while(top>=base)
{
int mid;
mid=(base+top)/2;
if(t==a[mid])
{
cout<<"YES"<<endl;
break;
}
else if(t>a[mid])
{
base=mid+1;
}
else
{
top=mid-1;
}
}
if(top<base)
{
cout<<"NO"<<endl;
}
}
}
return 0;
}
