質問編集履歴
1
不適切すぎる質問の仕方を直しました。
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
lower_boundとupper_boundの処理を知りたい
|
|
1
|
+
lower_boundとupper_boundの処理を知りたい。
|
test
CHANGED
|
@@ -22,55 +22,46 @@
|
|
|
22
22
|
sort(a.begin(), a.end());
|
|
23
23
|
sort(b.begin(), b.end());
|
|
24
24
|
sort(c.begin(), c.end());
|
|
25
|
-
|
|
26
|
-
|
|
27
|
-
|
|
28
|
-
|
|
29
25
|
// b[j] を固定して考える
|
|
30
26
|
long long res = 0;
|
|
31
27
|
for (int j = 0; j < N; ++j) {
|
|
32
28
|
long long Aj = lower_bound(a.begin(), a.end(), b[j]) - a.begin();
|
|
29
|
+
cout << "lower_bound=" << *lower_bound(a.begin(), a.end(), b[j]) << endl;
|
|
30
|
+
cout << "a.begin=" << *a.begin() << endl;
|
|
33
|
-
|
|
31
|
+
cout << "Aj=" << Aj << endl;
|
|
34
32
|
long long Cj = N - (upper_bound(c.begin(), c.end(), b[j]) - c.begin());
|
|
35
|
-
std::cout << Cj << std::endl;
|
|
36
|
-
cout<<"
|
|
33
|
+
//cout << "N=" << N << endl;
|
|
34
|
+
//cout << "upper_bound=" << *upper_bound(c.begin(), c.end(), b[j]) << endl;
|
|
35
|
+
//cout << "Cj=" << Cj << endl;
|
|
37
36
|
res += Aj * Cj;
|
|
38
|
-
|
|
39
37
|
}
|
|
40
38
|
cout << res << endl;
|
|
41
39
|
}
|
|
42
40
|
```
|
|
41
|
+
### 入力
|
|
42
|
+
3
|
|
43
|
+
1 1 1
|
|
44
|
+
2 2 2
|
|
45
|
+
3 3 3
|
|
46
|
+
|
|
43
47
|
|
|
44
48
|
### 出力結果
|
|
45
|
-
```ここに言語を入力
|
|
46
|
-
2
|
|
47
|
-
5
|
|
48
|
-
|
|
49
|
+
lower_bound=33
|
|
50
|
+
a.begin=1
|
|
49
|
-
3
|
|
51
|
+
Aj=3
|
|
50
|
-
5
|
|
51
|
-
|
|
52
|
+
lower_bound=33
|
|
53
|
+
a.begin=1
|
|
52
|
-
|
|
54
|
+
Aj=3
|
|
53
|
-
4
|
|
54
|
-
|
|
55
|
+
lower_bound=33
|
|
55
|
-
5
|
|
56
|
-
3
|
|
57
|
-
|
|
56
|
+
a.begin=1
|
|
58
|
-
5
|
|
59
|
-
3
|
|
57
|
+
Aj=3
|
|
60
|
-
------------
|
|
61
|
-
6
|
|
62
|
-
2
|
|
63
|
-
------------
|
|
64
|
-
|
|
58
|
+
27
|
|
65
|
-
```
|
|
66
|
-
自分の調べた上での予想だとソートしたうえで、keyとなるデータ（今回はソートしたｂの配列のｊ番目）をＡとＣに挿入したとき、
|
|
67
|
-
lower_boundは左側、upper_boundは右側という解釈なので、
|
|
68
|
-
ひとつ目の出力は、Aj=３、Cj＝56 となる予想でした。
|
|
69
59
|
|
|
60
|
+
プログラム上だと、``` long long Aj = lower_bound(a.begin(), a.end(), b[j]) - a.begin();```
|
|
61
|
+
なので、Aj＝33－1＝３２じゃないのでしょうか。
|
|
62
|
+
また、なぜ、ずっと33なのでしょうか...
|
|
70
63
|
### 試したこと
|
|
71
|
-
|
|
72
|
-
|
|
64
|
+
Aj、lower＿boundを出力。
|
|
73
|
-
resを除外。
|
|
74
65
|
|
|
75
66
|
### 補足情報（FW/ツールのバージョンなど）
|
|
76
67
|
|