PAT L 2-012.ヒープについての判断【データ構造】
テーマリンク
https://www.patest.cn/contests/gplt/L2-012
考え方
問題自体は難しくないですが、文字列処理はちょっと煩わしいです.大きな穴があります.つまり、プッシュしながらヒープを作らなければならないです.一度に読んでから積み上げることはできません.両者が作る順番は違います.そのために十数回も変えました.ここでSTLのメークを使いました.heap、自分で書いてもいいです.そんなに長くないです.
ACコード
https://www.patest.cn/contests/gplt/L2-012
考え方
問題自体は難しくないですが、文字列処理はちょっと煩わしいです.大きな穴があります.つまり、プッシュしながらヒープを作らなければならないです.一度に読んでから積み上げることはできません.両者が作る順番は違います.そのために十数回も変えました.ここでSTLのメークを使いました.heap、自分で書いてもいいです.そんなに長くないです.
ACコード
#include
#include
#include
#include
#include
#include
#include
using namespace std;
vector<int>heap;
int find(int a)
{
return distance(heap.begin(), find(heap.begin(), heap.end(), a));
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while (n--)
{
int t;
scanf("%d", &t);
heap.push_back(t);
make_heap(heap.begin(), heap.end(), greater<int>());
}
getchar();
while (m--)
{
string q;
getline(cin, q);
if (q[q.length() - 1] == 't')
{
int a;
stringstream ss(q);
ss >> a;
if (heap[0] == a) printf("T
");
else printf("F
");
}
else if (q[q.length() - 1] == 's')
{
int a, b;
string temp;
stringstream ss(q);
ss >> a >> temp >> b;
int pos_a = find(a);
int pos_b = find(b);
pos_a++; pos_b++;
if (pos_a / 2 == pos_b / 2)
{
printf("T
");
}
else
{
printf("F
");
}
}
else
{
stringstream ss(q);
int a, b;
string temp;
ss >> a >> temp >> temp;
if (temp[0] == 't')
{
ss >> temp >> temp >> b;
int pos_a = find(a);
int pos_b = find(b);
if (pos_b == pos_a * 2 + 1 || pos_b == pos_a * 2 + 2)
{
printf("T
");
}
else
{
printf("F
");
}
}
else if (temp[0] == 'a')
{
ss >> temp >> temp >> b;
int pos_a = find(a);
int pos_b = find(b);
if (pos_a == pos_b * 2 + 1 || pos_a == pos_b * 2 + 2)
{
printf("T
");
}
else
{
printf("F
");
}
}
}
}
return 0;
}