白駿3020号ホタル(C++)
2560 ワード
この探索とますます親しくなってきた...
何してるの...?メッセージが送れる程度…?ゴロゴロ鳴る
最近、時間を計って問題を解く練習をしています.
この問題の核心low boundを把握するにはupper boundで13分かかりますが、その後47分の挿入が行われ、合計1時間かかりました...
入力順によって障害物はタケノコ,鍾乳石に分けられ,それぞれ入力を受けて並べ替えられた後,low bound,upper boundを用いた.
上記2つのアルゴリズムの時間的複雑度はlognであり,すべての高さセグメントで破壊する必要がある障害物の個数を求める必要があるため,総時間的複雑度はh*lognである.
基準高さより小さい石筍個数(s)を求め,洞窟高さから基準高さを超えない鍾乳石個数(e)を減算し,これを全個数から減算して照合した.以下に示すように、画像として表示します.
例えば、基準高さが4の場合、4未満のタケノコ個数(s)が2個、洞窟高さで基準高さ(7−4=3)を超えない鍾乳石個数(e)が2個であるため、障害物個数(6)全体においてsとeの2値高さを4とすると、破壊すべき障害物個数となる.
この部分で私もずっと混同していたので、また20分ほど無駄にしたようです.
時間を計りながら問題を解くのはもっと焦りましたもっとリラックスして
何してるの...?メッセージが送れる程度…?ゴロゴロ鳴る
最近、時間を計って問題を解く練習をしています.
この問題の核心low boundを把握するにはupper boundで13分かかりますが、その後47分の挿入が行われ、合計1時間かかりました...
문제링크
https://www.acmicpc.net/problem/3020 설명
これはホタルが破壊する障害物の最大値と,これらの区間の個数を求める必要があるという問題である.入力順によって障害物はタケノコ,鍾乳石に分けられ,それぞれ入力を受けて並べ替えられた後,low bound,upper boundを用いた.
上記2つのアルゴリズムの時間的複雑度はlognであり,すべての高さセグメントで破壊する必要がある障害物の個数を求める必要があるため,総時間的複雑度はh*lognである.
基準高さより小さい石筍個数(s)を求め,洞窟高さから基準高さを超えない鍾乳石個数(e)を減算し,これを全個数から減算して照合した.以下に示すように、画像として表示します.
例えば、基準高さが4の場合、4未満のタケノコ個数(s)が2個、洞窟高さで基準高さ(7−4=3)を超えない鍾乳石個数(e)が2個であるため、障害物個数(6)全体においてsとeの2値高さを4とすると、破壊すべき障害物個数となる.
この部分で私もずっと混同していたので、また20分ほど無駄にしたようです.
時間を計りながら問題を解くのはもっと焦りましたもっとリラックスして
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> stalactite, stalagmite, ans(500001);
int n, h, num, s, e, m, mincnt = 200000;
void input()
{
cin >> n >> h;
for (int i = 0; i < n; i++)
{
cin >> num;
if (i % 2)
stalactite.push_back(num);
else
stalagmite.push_back(num);
}
sort(stalagmite.begin(), stalagmite.end());
sort(stalactite.begin(), stalactite.end());
}
void solution()
{
for (int i = 1; i <= h; i++)
{
s = upper_bound(stalactite.begin(), stalactite.end(), h - i) - stalactite.begin();
e = lower_bound(stalagmite.begin(), stalagmite.end(), i) - stalagmite.begin();
mincnt = min(mincnt, n - s - e);
ans[n - s - e]++;
}
cout << mincnt << ' ' << ans[mincnt];
}
void solve()
{
input();
solution();
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
Reference
この問題について(白駿3020号ホタル(C++)), 我々は、より多くの情報をここで見つけました https://velog.io/@ngchaneok/백준-3020번-개똥벌레-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol