You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
89 lines
2.2 KiB
89 lines
2.2 KiB
2 years ago
|
# Sever the Skyline
|
||
|
|
|
||
|
|
### 题目描述
|
||
|
|
「被废弃的城市」中心有一台「不知所谓的机器」。机器顶端天线上的灯泡隐隐约约地散发着光芒。
|
||
|
|
|
||
|
|
云浅发现灯泡每次闪烁后发出的颜色有一定的规律。
|
||
|
|
|
||
|
|
具体来说，灯泡每次闪烁后的颜色可以用 $n$ 个二元组 $(a_1,b_1),(a_2,b_2),\cdots,(a_n,b_n)$ 来表示。机器会对每个 $i=1,2,3,\cdots,n$ 闪烁 $a_i$ 次，并且这 $a_i$ 次闪烁发出的颜色都为 $b_i$。
|
||
|
|
|
||
|
|
现在云浅想知道，机器第 $m$ 次闪烁后，发出的颜色是什么。
|
||
|
|
|
||
|
|
### 输入格式
|
||
|
|
|
||
|
|
第一行两个正整数 $n,m$。
|
||
|
|
|
||
|
|
第二行 $n$ 个正整数 $a_1,\cdots,a_n$。
|
||
|
|
|
||
|
|
第三行 $n$ 个正整数 $b_1,\cdots,b_n$。
|
||
|
|
|
||
|
|
### 输出格式
|
||
|
|
|
||
|
|
输出一行一个正整数表示答案。
|
||
|
|
|
||
|
|
### 数据范围
|
||
|
|
|
||
|
|
对于 $100\%$ 的数据，$1\le n\le 10^5,1\le m,a_i,b_i\le 10^9,m\le \sum a_i$。
|
||
|
|
|
||
|
|
| 测试点编号 | $n$ | $a_i$ | 其他 |
|
||
|
|
| :-: | :-: | :-: | :-: |
|
||
|
|
| $1\sim 3$ | $\le 100$ | $\le 100$ | 无 |
|
||
|
|
| $4\sim 5$ | $\le 1000$ | $\le 1000$ | 无 |
|
||
|
|
| $6\sim 8$ | $\le 10^5$ | $\le 10^5$ | $m\le 10^6$ |
|
||
|
|
| $9\sim 10$ | $\le 10^5$ | $\le 10^9$ | 无 |
|
||
|
|
|
||
|
|
<div style="page-break-after: always"></div>
|
||
|
|
|
||
|
|
### 题解
|
||
|
|
找到最小的满足 $a_1+a_2+\cdots+a_k\ge m$ 的 $k$，输出 $b_k$ 即可。
|
||
|
|
|
||
|
|
复杂度 $O(n)$。
|
||
|
|
|
||
|
|
|
||
|
|
#### 参考代码
|
||
|
|
|
||
|
|
```c++{.line-numbers}
|
||
|
|
#include <bits/stdc++.h>
|
||
|
|
#define int long long
|
||
|
|
using namespace std;
|
||
|
|
inline int read() {
|
||
|
|
int x = 0, f = 1;
|
||
|
|
char c = getchar();
|
||
|
|
for (; (c < '0' || c > '9'); c = getchar()) {
|
||
|
|
if (c == '-') {
|
||
|
|
f = -1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
for (; (c >= '0'&& c <= '9'); c = getchar()) {
|
||
|
|
x = x * 10 + (c& 15);
|
||
|
|
}
|
||
|
|
return x * f;
|
||
|
|
}
|
||
|
|
int n, m;
|
||
|
|
const int MN = 1e5 + 5;
|
||
|
|
int a[MN], b[MN];
|
||
|
|
signed main(void) {
|
||
|
|
freopen("city.in", "r", stdin);
|
||
|
|
freopen("city.out", "w", stdout);
|
||
|
|
n = read();
|
||
|
|
m = read();
|
||
|
|
int x = 0;
|
||
|
|
for (int i = 1; i <= n; i++) {
|
||
|
|
a[i] = read();
|
||
|
|
}
|
||
|
|
for (int i = 1; i <= n; i++) {
|
||
|
|
b[i] = read();
|
||
|
|
}
|
||
|
|
for (int i = 1; i <= n; i++) {
|
||
|
|
x += a[i];
|
||
|
|
if (x >= m) {
|
||
|
|
cout << b[i] << endl;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
<div style="page-break-after: always"></div>
|