The 2021 ICPC Asia Regionals Online Contest (I) A Busiest Computing Nodes (二分+线段树)
2021/9/22 22:40:45
本文主要是介绍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; }
这篇关于The 2021 ICPC Asia Regionals Online Contest (I) A Busiest Computing Nodes (二分+线段树)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望