首页 > 代码库 > HDOJ 4671 Backup Plan 构造优先队列
HDOJ 4671 Backup Plan 构造优先队列
优先队列构造前两列....
Backup Plan
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 775 Accepted Submission(s): 365
Special Judge
Problem Description
Makomuno has N servers and M databases. All databases are synchronized among all servers and each database has a ordered list denotes the priority of servers to access. This list is guaranteed to be a valid permutation of all servers.
Every time someone wants to execute queries on a certain database, he will send a request to the first server in the list. If it‘s dead, he will simply turn to the next one. Otherwise a working copy of the database is found, and this copy is called active.
Now, given N and M, Makomuno wants to find a permutation for each database which could assure that all servers are load-balanced. Moreover, Makomuno hopes the system will be load-balanced even if exactly one server is broken.
Note that if we call the number of active copies on i-th server Ai, then load-balanced means max∣Ai - Aj∣≤1 for any i and j in non broken servers set. We won‘t consider broken servers in this case.
Every time someone wants to execute queries on a certain database, he will send a request to the first server in the list. If it‘s dead, he will simply turn to the next one. Otherwise a working copy of the database is found, and this copy is called active.
Now, given N and M, Makomuno wants to find a permutation for each database which could assure that all servers are load-balanced. Moreover, Makomuno hopes the system will be load-balanced even if exactly one server is broken.
Note that if we call the number of active copies on i-th server Ai, then load-balanced means max∣Ai - Aj∣≤1 for any i and j in non broken servers set. We won‘t consider broken servers in this case.
Input
The input contains several test cases, terminated by EOF.
Each test case has one line containing two integer N ( 2≤N≤100) and M ( 1≤M≤100).
Each test case has one line containing two integer N ( 2≤N≤100) and M ( 1≤M≤100).
Output
For each case output M lines, the i-th line contains a permutation of all servers, indicating the expected order. Servers are numbered from 1 to n.
Sample Input
5 3
Sample Output
2 4 3 1 5 1 5 4 2 3 3 5 2 4 1HintIn the sample test case, the active copies of these databases are on server 2,1 and 3 in normal state. A = {1,1,1,0,0} If server 1 or 3 has broken, server 5 will take its work. In case we lost server 2, the second database will use server 4 instead. A = {1,BROKEN,1,1,0} It‘s clear that in any case this system is load-balanced according to the plan in sample output.
Source
2013 Multi-University Training Contest 7
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> using namespace std; int n,m; int li[111][111]; bool have[111]; struct DUI { int x,s; bool operator < (const DUI xx) const { return s>xx.s; } }; int sum[111]; int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) { sum[i]=m/n+((i<=m%n)?1:0); } for(int u=1;u<=n;u++) { priority_queue<DUI> q; for(int i=1;i<=n;i++) { if(i==u) continue; q.push((DUI){i,sum[i]}); } for(int i=0;i<sum[u];i++) { int pos=u+i*n; DUI D=q.top(); q.pop(); li[pos][1]=D.x; D.s++; q.push(D); } } for(int i=1;i<=m;i++) { int c=i; while(c>n) c-=n; li[i][0]=c; } for(int i=1;i<=m;i++) { memset(have,false,sizeof(have)); have[li[i][0]]=true; have[li[i][1]]=true; int p=1; for(int j=2;j<n;j++) { while(have[p]==true) p++; li[i][j]=p; have[p]=true; } } for(int i=1;i<=m;i++) { for(int j=0;j<n;j++) { printf("%d%c",li[i][j],(j==n-1)?'\n':' '); } } } return 0; }
HDOJ 4671 Backup Plan 构造优先队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。