前提・実現したいこと
AtcoderのABC80のD問題について,作成したプログラムがシステムテストを通らない(誤りを含む)理由がわかりません.
使用言語はC++です.
方針
それぞれのチャンネルに対してmapを用いて番組の放送開始時間と終了時間をキーと値にとる.
すべての時刻で同時に録画器を動かす必要のある数を求め,その最大値が答えである.
ただし,同じチャンネルで連続した時間(ex.時刻1-3と時刻3-5)に番組がある場合,別々に計算すると放送前の待機時間0.5が重複してしまうため,1つの番組として扱う.
発生している問題・エラーメッセージ
基本的な挙動は正しいが,テストセットの一部でWA(誤った解が出力された状態)になる.
該当のソースコード
#include<iostream> #include <stdio.h> #include<string> #include <cmath> #include <algorithm> #include <vector> #include <cstdint> #include <queue> #include <map> #include <set> #define MOD 1000000007 #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr) #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; typedef long long ll; using namespace std; int main(){ int n,c; cin >> n >> c; map <int,int>channel[c+1]; REP(i,n){ int s,t,C; cin >> s >> t >> C; channel[C].insert({s,t}); } REP(i,c){ int key = 0,t = 0; ITR(itr,channel[i+1]){ if(itr->first == t){ // 連続した時間の番組があれば,1つにまとめる. channel[i+1][key] = itr->second; channel[i+1].erase(itr); } key = itr->first; t = itr->second; } } const int NMAX = 100010; int s[NMAX] = {}; REP(i,c){ ITR(itr,channel[i+1]){ s[itr->first-1]++; //待機時間があるため,録画器は番組開始の1手前の時刻から使用 s[itr->second]--; } } /* REP(i,c){ cout << i+1 << endl; ITR(itr,channel[i+1]){ cout << itr->first << " " << itr->second << endl; } } */ int ans = 0; REP(i,NMAX-1){ s[i+1] += s[i]; ans = max(ans,s[i+1]); } cout << ans << endl; return 0; }
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/05/30 13:46