Submission #61130


ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*HOJ 738 - プログラミング入門:二分探索*/
/*この問題の愚直な解放派、線形探索を行って、求めていくこと。しかし、この問題の場合は
制限時間を越えてしまうため、その危険性を回避するために、二分探索を行って、手間を少なくする。*/
#include <stdio.h>
signed main(){
int n=0,i=0,t=0;
int s[10001]={};
int ans[100001]={};
int a[100001]={};
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%d",&a[i]);
}
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&s[i]);
int low=-1;/*出力時は、予め、+1することを定めているため、*/
/*highの方にー1していないので、
固定地として変わらない、最低値にー1に代入した方が良い。*/
/*lowやhighは*/
int high=t;/*配列の用端を、lowとhighで、示している。
実行判断で配列外参照にならないように、ある程度LOWの方で、
1つ参照するために場所を増やしておく、*/
/*二文探索に関して言えば、求める数の一つ上の添い字の文字を求めることで、
それ以下にある値の数を求めることができる。*/
while(high-low>1){/*highとlowの範囲が1を下回った瞬間に、ループから抜け出す*/
/*while文では、先に条件を判定するため、もし抜けてしまった場合のために
30行目以降のprintf文にlow+1としている。*/
int mid=(high+low)/2;/*いま自分が見ている配列の位置を示している。*/
/*値が一つに決まるように示している。*/
/*宣言と同時に、関数内に式を入れている。*/
/*highとlowまでの間に何個の値があるのかを示してる。*/
if(a[mid]<=s[i]){/*条件を狭める方によって、OKやNOを選択していく。*/
low=mid;
}else{
high=mid;
}
}
ans[i]=low+1;
}
for(i=0;i<n;i++){
printf("%d\n",ans[i]);
}
return(0);
}
/*単調性(常に増え続けているなどの、一定の変化性)を
もっていものに対して、行うことができるのが、{二分探索}*/

ステータス

項目 データ
問題 0738 - プログラミング入門:二分探索
ユーザー名 <span style="color:#000000;font-weight:bold;">ei2031</span>
投稿日時 2020-07-20 16:50:05
言語 C
状態 Runtime Error
得点 2
ソースコード長 2506 Byte
最大実行時間 87 ms
最大メモリ使用量 1400 KB

セット

セット 得点 Cases
1 Linear Search 2 / 2 Input0[1-5]
2 Binary Search 0 / 8 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
Input01 AC 23 ms 1372 KB
1
2
Input02 AC 18 ms 1244 KB
1
2
Input03 AC 24 ms 1116 KB
1
2
Input04 AC 22 ms 1368 KB
1
2
Input05 AC 15 ms 1376 KB
1
2
Input06 RE 87 ms 1376 KB
2
Input07 RE 44 ms 1376 KB
2
Input08 RE 35 ms 1388 KB
2
Input09 RE 32 ms 1400 KB
2
Input10 RE 33 ms 1276 KB
2