Busiest Computing Nodes (线段树维护区间最小值)

谁借莪１个温暖的怀抱￠ 2022-09-12 14:44 131阅读 0赞

2021icpc 网络赛第一场a题

参考：[https://www.acwing.com/file\_system/file/content/whole/index/content/2958989/][https_www.acwing.com_file_system_file_content_whole_index_content_2958989]

题目大意：给定k个节点，每个节点可以运行有**起始时间**和**终止时间**的项目，每个项目到来都会询问第 （i%k， i %k+1, … 0 …i%k-1） 是否空闲，所有k个节点都没有空闲，这个项目跳过，否则按照访问的优先顺序，寻找到第一个合适的节点运行该项目，并更新这个节点的结束顺序。

思路：需要把每次询问控制在 log(k) 时间范围内。

访问顺序：  
先访问右边节点\[i%k , k\] ，  
再访问左边节点 \[0, i%k-1\]

ask函数返回 : 合适节点的**序号**

合适的定义：**时间合适** ， **位置合适**

时间合适：当前区间的最小值是否 <= 项目开始时间

位置合适：递归去查询左边的区间，遇到不适合，递归右边区间，得到就一定是合适的。

#include <iostream>
    #define ls (i<<1)
    #define rs (i<<1|1)
    #define ll long long
    const int N = 1e5 + 10;
    
    int k, n;
    int cnt[N];
    
    struct Node 
    { 
    	int l, r;
    	ll data;
    }tr[N<<2];
    
    inline void pushup(int i)
    { 
    	tr[i].data = std::min(tr[ls].data, tr[rs].data);
    }
    
    void build(int i, int l, int r)
    { 
    	tr[i].l = l, tr[i].r = r;
    	if(l == r) { tr[i].data = 0; return ;}
    	int mid = (l + r) >> 1;
    	build(ls,l,mid);
    	build(rs,mid+1,r);
    	pushup(i);
    }
    
    inline ll ask(int i, int l, int r, int k)
    { 
    	if(tr[i].l == tr[i].r) return tr[i].r;
    	if(tr[i].r < l or tr[i].l > r) return -1; 
    	
    	int res = -1; 
    	
    	if(tr[ls].r >= l and tr[ls].data <= (ll)k) res = ask(ls,l,r,k);
    	if(res == -1 and tr[rs].l <= r and tr[rs].data <= (ll)k) res = ask(rs,l,r,k);
    	return res;
    }
    
    inline void change(int i, int pos, int k)
    { 
    	if(tr[i].l == tr[i].r)
    	{ 
    		tr[i].data = k;
    		return ;
    	}
    	
    	if(tr[ls].r >= pos) change(ls, pos, k);
    	if(tr[rs].l <= pos) change(rs, pos, k);
    	pushup(i);
    }
    
    int main()
    { 
    	scanf("%d %d",&k, &n);
    	
    	build(1, 1, k);
    	
    	int res = 0;
    	
    	for(int i = 0; i < n; i++)
    	{ 
    		int now, t;
    		scanf("%d %d", &now, &t);
    		//std::cout << now << t << std::endl;
    		int pos = i % k;
    		ll t1 = ask(1, pos+1, k, now); // 线段树从1开始存储
    		if(t1==-1)
    		{ 
    			ll t2 = ask(1, 1, pos, now);
    			if(t2 != -1)
    			{ 
    				res = std::max(res, ++cnt[t2]);
    				change(1,t2,now+t);
    			}
    		}
    		else
    		{ 
    			res = std::max(res,++cnt[t1]);
    			change(1, t1, now+t);
    		}
    	}
    	
    	for(int i = 1; i <= k; i++)
    		if(res == cnt[i]) printf("%d ", i-1);
    	return 0;
    }

[https_www.acwing.com_file_system_file_content_whole_index_content_2958989]: https://www.acwing.com/file_system/file/content/whole/index/content/2958989/