PAT-撒狗粮
题目描述
网络上称一对情侣秀恩爱为“撒狗粮”,因为单身人士统称为“单身狗”。
在一个大型聚会上,所有宾客被安排坐在一张长条宴会桌边。如果一对情侣坐在一起,那么他们两人身边的单身狗就会被撒一脸狗粮;如果他们没有坐在一起,那么所有被夹在他们两人之间的单身狗都会被撒一脸狗粮。
本题就请你找出被撒狗粮最多(以“脸”为单位)的那位单身人士。
输入格式
输入第一行给出一个正整数 N(≤ 50 000),是已知情侣的对数;随后 N 行,每行给出一对情侣——为方便起见,每人对应一个 ID 号,为 5 位数字(从 00000 到 99999),ID 间以空格分隔;之后给出一个正整数 M(≤ 80 000),为参加派对的总人数;随后一行按座位从左到右的顺序给出这 M 位客人的 ID,以空格分隔。题目保证无人脚踩两条船。
输出格式
在一行中输出被撒狗粮最多的单身人士。如果不唯一,按 ID 递增顺序列出。ID 间用 1 个空格分隔,行的首尾不得有多余空格。
题目保证至少有一个输出。
输入样例
4
11111 22222
33333 44444
55555 66666
77777 88888
10
11111 33333 88888 22222 23333 55555 66666 10000 44444 12345
输出样例
10000 23333 88888
算法1
(暴力枚举) $O(n^2)$
最多只有13分。
算法2
(差分+排序) $O(nlogn)$
主要是一对情侣不在一起的时候,中间遍历逐个加会使得使得算法变成$O(n^2)$,因此考虑差分优化。
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
int n, m;
map<int, int> couple, idx;
int t[100010];
map<int, bool> stcouple, already;
int a, b;
vector<PII> anst;
void add(int a, int b)
{
anst[a].first += 1;
anst[b + 1].first -= 1;
}
bool cmp(PII a, PII b)
{
if (a.first != b.first)
return a.first > b.first;
else
return a.second < b.second;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &a, &b);
couple[a] = b, couple[b] = a;
}
scanf("%d", &m);
anst.push_back({0, -1});
for (int i = 1; i <= m; i++)
{
scanf("%d", &t[i]);
already[t[i]] = false;
stcouple[t[i]] = false;
idx[t[i]] = i;
anst.push_back({0, t[i]});
}
for (int i = 1; i <= m; i++)
stcouple[couple[t[i]]] = true;
for (int i = 1; i <= m; i++)
{
if (!stcouple[t[i]] || already[t[i]] == true || i + 1 > m)
continue;
if (t[i + 1] == couple[t[i]])
{
if (i - 1 > 0 && !stcouple[t[i - 1]])
add(i - 1, i - 1);
if (i + 2 < m + 1 && !stcouple[t[i + 2]])
add(i + 2, i + 2);
already[t[i]] = true;
already[couple[t[i]]] = true;
}
else
{
add(i + 1, idx[couple[t[i]]] - 1);
already[t[i]] = true;
already[couple[t[i]]] = true;
}
}
for (int i = 1; i <= m; i++)
anst[i].first += anst[i - 1].first;
for (int i = 1; i <= m; i++)
{
if (stcouple[anst[i].second])
{
anst[i].first = 0;
}
}
sort(anst.begin(), anst.end(), cmp);
int ansn = anst[0].first;
bool first = false;
for (int i = 0; i <= m; i++)
{
if (anst[i].first == ansn && anst[i].second != -1)
{
if (first)
printf(" ");
else
first = true;
printf("%05d", anst[i].second);
}
}
}
我感觉这题放l2都行。。。
陈越姥姥干的超级大模拟捏,但是又出了个差分算法。