BYTSE2 - spoj：私が間違っているかもしれないことをお勧めしますか？

Question

//BYTESE2 

#include<iostream> 
#include<vector> 
#include<algorithm> 
#include<cmath> 
using namespace std; 

typedef long long ll; 

bool compare(const ll &i, const ll &j) 
{ 
return (abs(i) < abs(j)); 
} 

int main() 
{ 
std::cout.sync_with_stdio(false); 
int t,n; 
cin>>t; 
while(t--) 
{ 
    vector <ll> v; 
    cin>>n; 
    if(n==0) 
    { 
     cout<<"0\n"; 
     continue; 
    } 
    ll start, end, i, j; 
    j=0; 
    for(i=0;i<n;i++) 
    { 
     cin>>start>>end; 
     v.push_back(start * 1); 
     v.push_back(end * -1); 
    } 
    sort(v.begin(), v.end(), compare); 
    int c=0, max=0; 
    vector <ll>::iterator it = v.begin(); 
    while(it != v.end()) 
    { 
     if(*it > 0) 
      c++; 
     else 
      c--; 
     if(max < c) 
      max = c; 
     it++; 
    } 
    cout<<max<<endl; 
} 
return 0; 
} 

現在の番号を格納する変数を使用します。ホール内のダンサーのすべての出口について、私は変数から減算しています。私はいくつかのテストケースを試しましたが、うまく動作しています。 しかし、提出すると、それは間違っていると言います！

私はこの質問をするために多くの方法を試みましたが無駄でした！ 私が間違っている可能性があることをお勧めします！ 質問へのリンク：http://www.spoj.com/problems/BYTESE2/

Answer 1

コードは完全にうまくいくようです。正の時間と負の時間として終了時間を保存するアプローチを好んだが、与えられた問題では時間が常に正ではない、つまりHagridがある負の数から時間を記録し始めているようであるその場合、開始時間と終了時間の両方が負になり、このアプローチで間違った答えが返されます。したがって、開始時刻であるか終了時刻であるかを保存するために、追加メモリを使用する必要があります。あなたのコードを次のように編集し、それが受け入れられました。

#include<iostream> 
#include<vector> 
#include<algorithm> 

using namespace std; 

bool compare(const pair<int, bool> &i, const pair<int, bool> &j) 
{ 
    return (i.first < j.first); 
} 

int main() 
{ 
    int t,n; 
    vector <pair<int, bool> > v; 
    cin>>t; 
    while(t--) 
    { 
     cin>>n; 

     int start, end, i, j; 
     j=0; 
     for(i=0;i<n;i++) 
     { 
      cin>>start>>end; 
      pair <int, bool> p1 (start, true); 
      pair<int, bool> p2 (end, false); 
      v.push_back(p1); 
      v.push_back(p2); 
     } 
     sort(v.begin(), v.end(), compare); 
     int c=0, max=0; 
     vector <pair<int, bool> >::iterator it = v.begin(); 
     while(it != v.end()) 
     { 
      if((*it).second) 
       c++; 
      else 
       c--; 
      if(max < c) 
       max = c; 
      it++; 
     } 
     cout<<max<<endl; 
     v.clear(); 
    } 
    return 0; 
}