PTA A_1097 Deduplication on a Linked List
传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805369774129152解：
链表+排序+哈希
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct Node{
int add, key, next, rank;
}node;
node a;
bool is_duplicated;
bool cmp(node a, node b)
{
return a.rank < b.rank;
}
int main(void)
{
int head, n;
scanf("%d %d", &head, &n);
for (int i = 0; i < n; i++)
{
int add;
scanf("%d", &add);
scanf("%d %d", &a.key, &a.next);
a.add = add;
}
int cnt = 0, rm_cnt = 0,j = -n * 2;
for (int i = head; i != -1; i = a.next)
{
a.rank = j++;
if (is_duplicated.key)])
{
rm_cnt++;
a.rank += n;
}
else
{
cnt++;
is_duplicated.key)] = true;
}
}
sort(a, a + 100010, cmp);
for (int i = 0; i < cnt - 1; i++)
printf("%05d %d %05d\n", a.add, a.key, a.add);
printf("%05d %d -1\n", a.add, a.key);
if (rm_cnt)
{
int last = cnt + rm_cnt - 1;
for (int i = cnt; i < last; i++)
printf("%05d %d %05d\n", a.add, a.key, a.add);
printf("%05d %d -1", a.add, a.key);
}
return 0;
}
页:
[1]