The 2021 ICPC Asia Regionals Online Contest (I) A Busiest Computing Nodes (二分+线段树)

  • The 2021 ICPC Asia Regionals Online Contest (I)  A Busiest Computing Nodes   (二分+线段树)

  • 题意:有\(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;
    }
    
    
上一篇:Python基础学习系列书籍_之排行


下一篇:“21天好习惯”第一期-4