线段树好题。传送门
这题细节较多,而且由于样例较弱,导致很难一次就完全理解题意,并实现。
解决本题大概分为几个步骤:
-
想清楚 $arrive time$,$process time$ 之间的关系并离散化处理。
-
线段树处理出区间中,所有处于闲置状态的机器的下标最小的哪一个。
-
利用$time$,数组处理出每一个变成闲置的机器。由于这一部分总的时间复杂度是均摊的因此,实际上,总的时间复杂度是可以接受的。
最后,实际上题目的题意较为模糊,导致理解了很久寻找机器的过程,以及实际上会抛弃部分询问。
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,k;
struct node{
int l,r,idx,col;
}tr[N*4];
void pushup(int u)
{
if(!tr[u<<1].col&&!tr[u<<1|1].col)tr[u].idx=min(tr[u<<1].idx,tr[u<<1|1].idx);
else if(!tr[u<<1].col)tr[u].idx=tr[u<<1].idx;
else if(!tr[u<<1|1].col)tr[u].idx=tr[u<<1|1].idx;
else tr[u].idx=k;
}//更新父亲节点的 最靠左侧的可使用机器。
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={l,r,l,0};//最开始所有的机器均处于闲置状态
}else
{
tr[u]={l,r,k,0};
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void update(int u,int x)
{
if(tr[u].l==x&&tr[u].r==x)
{
tr[u].col^=1;//改变机器状态
if(tr[u].col==0)tr[u].idx=x;
else tr[u].idx=k;
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid)update(u<<1,x);
else update(u<<1|1,x);
pushup(u);
}
}
int query_idx(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)return tr[u].idx;
else
{
int mid=tr[u].l+tr[u].r>>1;
int res=k;
if(l<=mid)res=query_idx(u<<1,l,r);
if(res!=k)return res;
if(r>mid)return query_idx(u<<1|1,l,r);
return res;
}
}
vector<int>nums;
int find(int x)
{
return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
vector<int>times[N];
#define st first
#define ed second
void solve()
{
cin>>k>>n;
build(1,0,k-1);//建树
vector<PII>q(n);
for(int i=0;i<n;i++)
{
cin>>q[i].st>>q[i].ed;
q[i].ed+=q[i].st;
nums.push_back(q[i].st);
nums.push_back(q[i].ed);
}
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());//离散化
for(int i=0;i<n;i++)q[i].st=find(q[i].st),q[i].ed=find(q[i].ed);
// for(int i=0;i<n;i++)cout<<q[i].st<<' '<<q[i].ed<<endl;
// cout<<endl;
int res=0,sum=k;
vector<int>a(k);
for(int i=0;i<n;i++)
{
while(res<=q[i].st)
{
if(times[res].size())for(auto c:times[res])update(1,c),sum++;
res++;
}//保证每次处理询问的时候至少会有一台机器是处于闲置状态
int cnt=k;
if(sum==0)continue;//加速询问
cnt=query_idx(1,i%k,k-1);
if(cnt!=k)
{
a[cnt]++,update(1,cnt);
times[q[i].ed].push_back(cnt);sum--;
continue;
}
if(i%k-1>=0)cnt=query_idx(1,0,i%k-1);
if(cnt!=k)
{
a[cnt]++,update(1,cnt);
times[q[i].ed].push_back(cnt);sum--;
}
}
// cout<<endl;
// for(int i=0;i<k;i++)cout<<i<<' '<<a[i]<<endl;
// cout<<endl;
// cout<<a[0]<<endl;
vector<int>ans;
int maxv=*max_element(a.begin(),a.end());
for(int i=0;i<k;i++)
if(a[i]==maxv)ans.push_back(i);
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
{
if(i)cout<<" ";
cout<<ans[i];
}
cout<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
solve();
return 0;
}