|
|
|
|
|
# [唱歌](https://www.jisuanke.com/problem/T3697)
|
|
|
|
|
|
|
|
|
|
|
|
### 题目描述
|
|
|
|
|
|
ame 是一个可爱的女孩子，她想要唱歌。
|
|
|
|
|
|
|
|
|
|
|
|
一共有 $n$ 首歌，第 $i$ 首歌的长度 $a_i$，同时唱第 $i$ 首歌的满意值为 $b_i$。
|
|
|
|
|
|
|
|
|
|
|
|
ame 喜欢的歌满足 $a_i\leq m$，同时有 $k$ 首歌 $c_1,c_2,\ldots,c_k$ 是 ame 不喜欢的。
|
|
|
|
|
|
|
|
|
|
|
|
其中 $1\leq c_i\leq n$，表示编号为 $c_i$ 的歌曲 ame 是不喜欢的。
|
|
|
|
|
|
|
|
|
|
|
|
请求出 ame 喜欢的歌中满意值第 $p$ 大的歌曲的编号，如果不存在输出 `aaaaaaaaa`。
|
|
|
|
|
|
|
|
|
|
|
|
### 输入格式
|
|
|
|
|
|
|
|
|
|
|
|
输入共四行。
|
|
|
|
|
|
|
|
|
|
|
|
第一行输入 $4$ 个正整数 $n,m,k,p$。
|
|
|
|
|
|
|
|
|
|
|
|
第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n$。
|
|
|
|
|
|
|
|
|
|
|
|
第三行输入 $n$ 个正整数 $b_1,b_2,...,b_n$。
|
|
|
|
|
|
|
|
|
|
|
|
第四行输入 $k$ 个正整数 $c_1,c_2,...,c_k$。
|
|
|
|
|
|
|
|
|
|
|
|
### 输出格式
|
|
|
|
|
|
|
|
|
|
|
|
输出共一行，输出满意值第 $p$ 大的歌曲的编号；若不存在，则输出 `aaaaaaaaa`。
|
|
|
|
|
|
|
|
|
|
|
|
### 数据范围
|
|
|
|
|
|
|
|
|
|
|
|
对于 $40\%$ 的数据，有 $1\leq n\leq 5,1\leq m\leq 10,1\leq a_i \leq m,k=0$。
|
|
|
|
|
|
|
|
|
|
|
|
对于另外 $30\%$ 的数据，有 $1\leq n\leq 10,0\leq k \leq n,1\leq a_i,b_i,m\leq 100$。
|
|
|
|
|
|
|
|
|
|
|
|
对于 $100\%$ 的数据，有 $1\leq n,p\leq 1000,0\leq k\leq n,1\leq c_i\leq n,1\leq a_i,b_i,m\leq 1000$，数据保证 $b_i$ 互不相同。
|
|
|
|
|
|
|
|
|
|
|
|
<div style="page-break-after: always"></div>
|
|
|
|
|
|
|
|
|
|
|
|
### 题解
|
|
|
|
|
|
|
|
|
|
|
|
首先除去不喜欢的歌，将喜欢的歌曲放入结构体中，再对结构体按照满意程度从大到小排序即可。
|
|
|
|
|
|
|
|
|
|
|
|
#### 参考代码
|
|
|
|
|
|
|
|
|
|
|
|
```c++{.line-numbers}
|
|
|
|
|
|
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1010;
|
|
|
|
|
|
int a[N], b[N], c[N];
|
|
|
|
|
|
/*
|
|
|
|
|
|
测试用例：
|
|
|
|
|
|
5 5 0 1
|
|
|
|
|
|
1 2 3 4 5
|
|
|
|
|
|
1 2 3 4 5
|
|
|
|
|
|
|
|
|
|
|
|
n=5 首歌
|
|
|
|
|
|
m=5 喜欢的歌长度小于5
|
|
|
|
|
|
k=0 没有不喜欢的
|
|
|
|
|
|
p=1 满意值第一大的是哪首歌
|
|
|
|
|
|
|
|
|
|
|
|
输入每首歌的长度a[i]
|
|
|
|
|
|
输入每首歌的喜欢程度值b[i]
|
|
|
|
|
|
|
|
|
|
|
|
答案：
|
|
|
|
|
|
5
|
|
|
|
|
|
*/
|
|
|
|
|
|
|
|
|
|
|
|
struct Node {
|
|
|
|
|
|
int id;
|
|
|
|
|
|
int value;
|
|
|
|
|
|
const bool operator<(const Node &b) const {
|
|
|
|
|
|
return value > b.value;
|
|
|
|
|
|
}
|
|
|
|
|
|
} d[N];
|
|
|
|
|
|
int dl;
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
// 必须符合计蒜客的输入输出要求，否则不能完成提交！
|
|
|
|
|
|
freopen("song.in", "r", stdin);
|
|
|
|
|
|
freopen("song.out", "w", stdout);
|
|
|
|
|
|
|
|
|
|
|
|
// n首歌，m:喜欢歌的长度a[i]<m,k：不喜欢歌的数量,p:满意值第p大
|
|
|
|
|
|
int n, m, k, p;
|
|
|
|
|
|
cin >> n >> m >> k >> p;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i]; // 歌的长度
|
|
|
|
|
|
for (int i = 1; i <= n; i++) cin >> b[i]; // 满意值
|
|
|
|
|
|
|
|
|
|
|
|
// 超过长度m限制不喜欢
|
|
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
|
|
|
if (a[i] > m) c[i] = 1;
|
|
|
|
|
|
|
|
|
|
|
|
// 特殊指定的不喜欢
|
|
|
|
|
|
for (int i = 1; i <= k; i++) {
|
|
|
|
|
|
int x;
|
|
|
|
|
|
cin >> x;
|
|
|
|
|
|
c[x] = 1; // 不喜欢,当桶用
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
|
|
|
if (!c[i]) d[dl++] = {i, b[i]};
|
|
|
|
|
|
sort(d, d + dl);
|
|
|
|
|
|
|
|
|
|
|
|
if (d[p - 1].value)
|
|
|
|
|
|
printf("%d\n", d[p - 1].id);
|
|
|
|
|
|
else
|
|
|
|
|
|
puts("aaaaaaaaa");
|
|
|
|
|
|
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
<div style="page-break-after: always"></div>
|
