BOJ-13904号
11276 ワード
アイデア
次第に分かることの一つは,例題を通してヒントを得,それを数式にすることが最も重要であるようだ.
まず例を見て、データを分析しました.
そのため、データの特徴を分析する必要がありますが、まずこの基準を残りの日付として考えます.
このような場合、残り時間の少ない課題から考えると、なんとか最高点数に達することはできない.
逆に,最後尾の課題から考えると,重なる日付がなければ排除できる.
(たとえば、最後尾のタスクが6日しか残っておらず、残りの6日のタスクが存在しない場合)
この場合,オーバーラップする場合が最大の問題となる.
このオーバーラップを解決するために,後からもう一度例を代入して解き,その結果,最高点数から解決すればよい解法が得られた.
しかし、この日は、時間が経った課題を考えるべきではありません.
すなわち,前からではなく後ろから考える条件によって問題を解決すべきである.
解法
注意点は極端なものを入れると気づくことが多い.たとえば、データ...私が言ったのは.
1)
すなわち、条件チェック部(
このため、次のコードが追加されました.
つまり,
2)
例を通したが、コミット時に実行時エラーが発生したのは、コードの間に
だから、上のコードのように
次第に分かることの一つは,例題を通してヒントを得,それを数式にすることが最も重要であるようだ.
まず例を見て、データを分析しました.
そのため、データの特徴を分析する必要がありますが、まずこの基準を残りの日付として考えます.
このような場合、残り時間の少ない課題から考えると、なんとか最高点数に達することはできない.
逆に,最後尾の課題から考えると,重なる日付がなければ排除できる.
(たとえば、最後尾のタスクが6日しか残っておらず、残りの6日のタスクが存在しない場合)
この場合,オーバーラップする場合が最大の問題となる.
このオーバーラップを解決するために,後からもう一度例を代入して解き,その結果,最高点数から解決すればよい解法が得られた.
しかし、この日は、時間が経った課題を考えるべきではありません.
すなわち,前からではなく後ろから考える条件によって問題を解決すべきである.
解法
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
int main() {
int homework_num;
vector<pair<int, int>> homework, temp;
cin >> homework_num;
for (int i = 0; i < homework_num; i++) {
int x, y;
cin >> x >> y;
homework.push_back({ x, y });
}
sort(homework.begin(), homework.end());
for (int day = homework.back().first; day > 0; day--) {
if (homework.empty())
break;
int max_score_index = homework.size() - 1;
int max_score = homework[max_score_index].second;
for (int i = max_score_index; homework[i].first >= day; i--) {
if (max_score < homework[i].second) {
max_score = homework[i].second;
max_score_index = i;
}
if (i == 0)
break;
}
if (homework.back().first >= day) {
temp.push_back(homework[max_score_index]);
homework.erase(homework.begin() + max_score_index);
}
}
// homework에서 뒤에서부터 day보다 작은것들 (기한이 지난것들)은 고려하지 않는다.
int max = 0;
for (int i = 0; i < temp.size(); i++)
max += temp[i].second;
cout << max;
return 0;
}
注意点注意点は極端なものを入れると気づくことが多い.たとえば、データ...私が言ったのは.
1)
i==-1
これはコードが完了してから初めて発見されたエラーです.for (int i = max_score_index; homework[i].first >= day; i--)
上記のコードでは、対応するfor文がi==0
に動作すると、i--
からi==-1
になる.すなわち、条件チェック部(
homework[i].first >= day
)が誤って参照を破棄したためにエラーとなる.このため、次のコードが追加されました.
if (i == 0)
break;
この場合、forクエリに残りがあるかどうか心配ですが、よく考えてみるとi
が0
になっています.これは、条件チェック部分にday
以上の日付が存在しないことを意味します.そのため、提出期限を超えた課題以外に課題はありません.つまり,
break
を直接やっても差し支えないと考える.2)
empty()
2番目に発見されたエラー.例を通したが、コミット時に実行時エラーが発生したのは、コードの間に
homework.erase()
が提供され、ジョブが空になった場合を考慮していないためである.だから、上のコードのように
if (homework.empty())
break;
追加しました.Reference
この問題について(BOJ-13904号), 我々は、より多くの情報をここで見つけました https://velog.io/@abrahamkim98/BOJ-13904번テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol