首页 > 代码库 > hiho 第155周 任务分配
hiho 第155周 任务分配
最小路径覆盖会超时;
贪心思路:
按照开始时间排序,然后根据结束时间,维护一个以结束时间的单调递增的队列,每次与最快结束的任务进行比较即可;
/*#include <cstdio>#include <algorithm>#include <cmath>#include <vector>#include <cstring>using namespace std;const int maxn = 100000+5;struct BPM { int n,m; vector<int> G[maxn]; int left[maxn]; bool T[maxn]; int right[maxn]; bool S[maxn]; void init(int n,int m) { this->n = n; this->m = m; for(int i=0;i<n;i++) G[i].clear(); } void AddEdge(int u,int v) { G[u].push_back(v); } bool match(int u) { S[u] = true; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(!T[v]) { T[v] = true; if(left[v]==-1||match(left[v])) { left[v] = u; right[u] = v; return true; } } } return false; } int solve() { memset(left,-1,sizeof(left)); memset(right,-1,sizeof(right)); int ans = 0; for(int u=0;u<n;u++) { memset(S,0,sizeof(S)); memset(T,0,sizeof(T)); if(match(u)) ans++; } return ans; }}sol;struct Node { int s,e;}node[maxn];int main(){ int n; scanf("%d",&n); sol.init(n,n); for(int i=0;i<n;i++) scanf("%d%d",&node[i].s,&node[i].e); for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(node[i].e<=node[j].s) sol.AddEdge(i,j); else if(node[i].s>=node[j].e) sol.AddEdge(j,i); printf("%d\n",n-sol.solve()); return 0;}*/#include <bits/stdc++.h>using namespace std;const int maxn = 100000+5;struct Node { int s,e; bool operator < (const Node & rhs) const { return s < rhs.s; }}node[maxn];int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&node[i].s,&node[i].e); sort(node,node+n); priority_queue<int,vector<int>,greater<int> > Q; Q.push(node[0].e); for(int i=1;i<n;i++) { if(Q.top()<=node[i].s) { Q.pop(); Q.push(node[i].e); } else Q.push(node[i].e); } printf("%d\n",Q.size()); return 0;}
hiho 第155周 任务分配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。