2008. 查询

用标记数组做。

排序完成后用二分查找做

include

include

include

using namespace std;
string query(int *a, int len, int key){
int middle;
int low = 0;
int high = len -1;
while(low <= high){
middle = (low + high) / 2;
if(key < a[middle]){
high = middle - 1;
}
if(key > a[middle]){
low = middle + 1;
}
if(key == a[middle]){
return “yes!”;
}
}
return “no!”;
}

int main()
{
int n_in;
cin >> n_in;
int i;
int a[n_in];
for(i = 0; i < n_in; i++){
cin >> a[i];
}
sort(a, a + n_in);// 默认升序
int n_qry;
cin >> n_qry;
int q[n_qry];
for(i = 0; i < n_qry; i++){
cin >> q[i];
}
for(i = 0; i < n_qry; i++){
string res = query(a, n_in, q[i]);
cout << res << endl;
}
return 0;
}

请教下：

define _CRT_SECURE_NO_WARNINGS

pragma warning(disable:4996)

include

include

include

include

typedef struct
{
unsigned int m;
unsigned int n;
char m_x[500];
char n_x[500];
}rec_dat;

typedef enum
{
M_FLAG = 0,
M_REC,
N_FLAG,
N_REC,
DEAL
}rec_status;

if 1

void main()
{
char bug = 0;
//char bug_p = &bug
static rec_status rec_check = M_FLAG;
static rec_dat rec_data;
unsigned int n_num = 0;
unsigned int m_num = 0;
unsigned int result = 0;
while (1) {
if (scanf(“%d”, &bug) != 0)
{
switch (rec_check)
{
case M_FLAG:
//rec_data.m = atoi(&bug);
rec_data.m = bug;
rec_check = M_REC;
break;
case M_REC:
rec_data.m_x[m_num] = bug;
m_num = m_num + 1;
if (rec_data.m == m_num)
{
rec_check = N_FLAG;
m_num = 0;
}
break;
case N_FLAG:
//sprintf((char)rec_data.n, “%d”, &bug);
//rec_data.n = atoi(&bug);
rec_data.n = bug;
rec_check = N_REC;
break;
case N_REC:
rec_data.n_x[n_num] = bug;
n_num = n_num + 1;
if (rec_data.n <= n_num)
{
rec_check = DEAL;
n_num = 0;
}
else
break;
case DEAL:
for (unsigned int i = 0; i < rec_data.n; i++)
{
if (strchr(&rec_data.m_x[0], rec_data.n_x[i]) == NULL)
printf(“no!\r\n”);
else
printf(“yes!\r\n”);
}
rec_check = M_FLAG;
break;
default:
break;
}
}
}
}

endif

if 0

void main()
{
rec_dat rec_data;
unsigned int result = 0;
char bug = 0;
while (1)
{
scanf(“%d”, &rec_data.m);
for (unsigned int i = 0; i < rec_data.m; i++)
{
scanf(“%d”, &rec_data.m_x[i]);
}
scanf(“%d”, &rec_data.n);
for (unsigned int i = 0; i < rec_data.n; i++)
{
scanf(“%d”, &rec_data.n_x[i]);
for (unsigned int j = 0; j < rec_data.m; j++)
{
if (rec_data.m_x[j] == rec_data.n_x[i])
{
rec_data.n_x[j] = 1;
break;
}
}
}
for (unsigned int i = 0; i < rec_data.n; i++)
{
if (rec_data.n_x[i] == 1)printf(“yes!\r\n”);
else printf(“no!\r\n”);
result = 0;
}
}
}

endif

两种方法都超时，大神可以帮忙看下原因吗

这题是一道搜索（字典）题，又没有顺序要求，所以用哈希表是最自然的想法。另一方面由于数据量太小了，所以直接对应就好了，连哈希表都不用的。

#include "bits/stdc++.h"
using namespace std;

int main() {
    bool given[501];
    memset(given, false, sizeof(given));
    uint32_t m; cin >> m;
    for (uint32_t i = 0; i < m; ++i) {
        uint32_t temp; cin >> temp;
        given[temp] = true;
    }
    uint32_t n; cin >> n;
    for (uint32_t i = 0; i < n; ++i) {
        uint32_t query; cin >> query;
        puts(given[query] ? "yes!" : "no!");
    }
}