You have a computing cluster with a total of k computing nodes, labelled from 0 to k−1. The cluster can handle multiple requests at the same time, but each node can process at most one request at the same time.
The rules for request assignment to computing nodes are as follows. Assume the i-th (i starts from 0) request arrives. If all nodes are occupied, the request is discarded (not processed at all). If the (i%k)-th node is available, it will process the request. Otherwise, the request will check the availability of the next node at (i 1)%k, (i 2)%k, and so on, until it finds an idle node.
Given a set of requests with their arrival time and the processing time, your task is to find the busiest computing nodes. A node that belongs to the busiest nodes when no other nodes serve more requests than it does.
输入描述The first line includes k and n, representing the size of the cluster and the number of requests.
Each of the next n lines includes two positive integers, representing the arrival time and the processing time of a request.
The input data satisfy that 1≤k,n≤100,000, and 1≤arrival_time,processing_time≤1,000,000,000.
The requests are given in non-decreasing order of arrival time.
输出描述Print the labels of all the busiest nodes in lexicographic numerical order, separated by spaces.
样例输入
3 5
输出
1题意
给定k个处理机 从0到n-1编号 n个作业 按到达时间从0到n-1编号 的到达时间和处理时间。按序调度 第i个作业 若所有处理机都被占用 则丢弃作业 否则从第i%k个处理机开始检查到i%k 1 i%k 2…直至找到空闲的处理机。输出被占用次数最多的处理机的编号 可能有多个 按数字从小到大输出。
思路这题属实阅读理解 比赛中是真的看不懂 写了半天假题 最后才看出来是线段树 二分。用线段树维护k个处理机上作业完成时间的区间最小值 区间查询 单点修改 然后二分查找区间查询的右端点 先查k的右边 此时左端点为i%k 若没查到则再查k的左边 此时左端点为1 若还没查到则丢弃该作业。
代码#include bits/stdc .h
using namespace std;
const int N 1e5 5;
int n,k;
int a[N],b[N];
int ans[N];
vector int v;
struct node {
int l,r,s;
} tr[N 2];
void pushup(int u) {
tr[u].s min(tr[u 1].s,tr[u 1|1].s);
void build(int u,int l,int r) {
tr[u] {l,r,0};
if(l r) return;
int mid l r 1;
build(u 1,l,mid);
build(u 1|1,mid 1,r);
pushup(u);
void modify(int u,int l,int r,int x,int y) {
if(l r l x) {
tr[u].s y;
return;
int mid l r 1;
if(x mid) modify(u 1,l,mid,x,y);
else modify(u 1|1,mid 1,r,x,y);
pushup(u);
int query(int u,int l,int r) {
if(tr[u].l l tr[u].r r) {
return tr[u].s;
int mid tr[u].l tr[u].r 1;
int res 0x3f3f3f3f;
if(l mid) res min(res,query(u 1,l,r));
if(r mid) res min(res,query(u 1|1,l,r));
pushup(u);
return res;
int main() {
cin k n;
for(int i 1; i n; i ) cin a[i] b[i];
build(1,1,k);
for(int j 0; j n; j ) {
int i j 1;
int l j%k 1,r k 1;
while(l r) {
int mid l r 1;
if(mid! k 1 query(1,j%k 1,mid) a[i]) r mid;
else l mid 1;
if(l! k 1) {
modify(1,1,k,l,b[i] a[i]);
ans[l] ;
} else {
l 1,r j%k 1;
while(l r) {
int mid l r 1;
if(mid! j%k 1 query(1,1,mid) a[i]) r mid;
else l mid 1;
if(l! j%k 1) {
modify(1,1,k,l,b[i] a[i]);
ans[l] ;
int xmax 0;
for(int i 1; i k; i ) xmax max(xmax,ans[i]);
for(int i 1; i k; i )
if(ans[i] xmax) v.push_back(i-1);
cout v[0];
for(int i 1;i v.size();i ) cout v[i];
原题链接
