Codeforces 1379 D.New Passenger Trams——尺取
12628 ワード
This way
タイトル:
現在の星の1日はh時間があり、1時間はm分があり、今は2種類の車が運転されています.赤い車は30分ごとに運転され、k分ごとに再開する準備ができています.そして、最初のバスの開始時間を決めることができます.今は青い車の時刻表があります.準備時間がありません.そして赤い車の時間と重なるとキャンセルされます(端点は計算されません)、最初の赤い車の開始時間はどのくらいで最小の青い車の数をキャンセルすることができますか?
問題:
私は本当にこのabに気絶して、c問題ができたときはもう終わります.この問題は全然見る時間がありません.実はすべて简単な问题で、しかし私はcfを打たないとこんなに紧张する时间に适応できません.この問題はhが役に立たないことを発見することができて、私達はm 2frac{m}{2}2 mを1つの循環と見なすことができて、30分ごとに赤い車が発車するためです.その後、すべての青い車を時間%m 2frac{m}{2}2 mで並べ替えた後、尺取すればよい.
タイトル:
現在の星の1日はh時間があり、1時間はm分があり、今は2種類の車が運転されています.赤い車は30分ごとに運転され、k分ごとに再開する準備ができています.そして、最初のバスの開始時間を決めることができます.今は青い車の時刻表があります.準備時間がありません.そして赤い車の時間と重なるとキャンセルされます(端点は計算されません)、最初の赤い車の開始時間はどのくらいで最小の青い車の数をキャンセルすることができますか?
問題:
私は本当にこのabに気絶して、c問題ができたときはもう終わります.この問題は全然見る時間がありません.実はすべて简単な问题で、しかし私はcfを打たないとこんなに紧张する时间に适応できません.この問題はhが役に立たないことを発見することができて、私達はm 2frac{m}{2}2 mを1つの循環と見なすことができて、30分ごとに赤い車が発車するためです.その後、すべての青い車を時間%m 2frac{m}{2}2 mで並べ替えた後、尺取すればよい.
#include
using namespace std;
#define ll long long
const int N=1e5+5;
struct node{
int id;
ll m;
bool operator< (const node& a)const {
return m<a.m;
}
}p[N*2];
deque<int>dq;
int main()
{
int n;
ll h,m,k,h1;
scanf("%d%lld%lld%lld",&n,&h,&m,&k);
m/=2;
for(int i=1;i<=n;i++)
scanf("%lld%lld",&h1,&p[i].m),p[i].id=i,p[i].m%=m;
sort(p+1,p+1+n);
for(int i=1;i<=n;i++)
p[i+n]=p[i],p[i+n].m+=m;
int l=2,del=n,sz=0,sta=0;
int lef=0,rig=0;
for(int i=1;i<=n;i++){
if(dq.size()&&dq.front()==p[i].id)
dq.pop_front(),sz--;
l=max(l,i+1);
while(p[l].m<=p[i].m+k-1)
dq.push_back(p[l++].id),sz++;
if(sz<del){
if(dq.size())
lef=i+1;
del=sz,sta=(p[i].m+k)%m;
}
}
printf("%d %d
",del,sta);
if(del){
for(int i=lef;i<=lef+del-1;i++)
printf("%d ",p[i].id);
}
printf("
");
return 0;
}