-
题意:有\(k\)个机器,下标\([0,k-1]\),现在有\(n\)个任务,每次给你起始时刻和持续时间,第\(i\)个任务从第\(i\mod k\)个机器开始,如果当前机器没有任务在进行,则执行这个任务,否则去找\((i+1)\mod k\),....,如果所有机器都在执行任务,则忽略这个任务,所有任务询问完后,问你哪些机器执行任务的次数最多。
-
题解:先借成一个\(2*k\)的数组,然后对于每个询问,找\([i\mod k,i\mod k+k-1]\)的最靠近左区间,切满足大小不大于\(x\)的位置,贡献++,然后更新这个值,这个操作可以先二分,然后线段树check,线段树维护的是区间最小值,每次单点修改,区间查询。
-
代码:
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define me memset #define rep(a,b,c) for(int a=b;a<=c;++a) #define per(a,b,c) for(int a=b;a>=c;--a) const int N = 1e6 + 10; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; using namespace std; typedef pair<int,int> PII; typedef pair<ll,ll> PLL; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll lcm(ll a,ll b) {return a/gcd(a,b)*b;} int k,n; int mx; int cnt[N]; struct Node{ //维护区间最小值 int l,r; ll val; }tr[N<<4]; void push_up(int u){ tr[u].val=min(tr[u<<1].val,tr[u<<1|1].val); } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,0}; return; } tr[u]={l,r,0}; int mid=(l+r)>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); push_up(u); } void update(int u,int x,ll val){ if(tr[u].l==tr[u].r){ tr[u].val=val; return; } int mid=(tr[u].l+tr[u].r)>>1; if(x<=mid) update(u<<1,x,val); else update(u<<1|1,x,val); push_up(u); } ll query(int u,int l,int r){ if(tr[u].l>=l && tr[u].r<=r){ return tr[u].val; } int mid=(tr[u].l+tr[u].r)>>1; ll res=INF; if(l<=mid) res=query(u<<1,l,r); if(r>mid) res=min(res,query(u<<1|1,l,r)); return res; } int main() { scanf("%d %d",&k,&n); build(1,0,2*k-1); for(int i=0;i<n;++i){ ll x,y; scanf("%lld %lld",&x,&y); int l=i%k,r=i%k+k-1; if(query(1,l,r)>x){ continue; } while(l<r){ //tight R int mid=(l+r)>>1; if(query(1,l,mid)<=x) r=mid; else l=mid+1; } update(1,l,x+y),update(1,(l+k)%(2*k),x+y); mx=max(mx,++cnt[l%k]); } vector<int> v; for(int i=0;i<n;++i){ if(cnt[i]==mx){ v.pb(i); } } for(int i=0;i<(int)v.size();++i){ printf("%d",v[i]); if(i!=(int)v.size()-1) printf(" "); } return 0; }