hdu 4671 Backup Plan 구조

2472 단어
진니마갱 문제는 세 사람이 한 시간 넘게 읽어서야 뜻을 알았다.
n개의 서버, m개의 임무를 주고 모든 임무에 우선순위 대기열을 만들어 줍니다. 모든 임무는 앞에 있는 서버를 우선적으로 선택하여 서비스를 제공합니다.
우리는 서버 임무를 고르게 분담해야 한다. 즉, 가장 많은 임무를 얻은 서버의 임무 수는 가장 적은 임무를 얻은 서버의 임무 수보다 1을 초과할 수 없다.
현재, 한 대의 서버가 고장날 것이다. (그러면 서비스가 필요한 작업은 대기열 뒤로 가서 다음 서버를 선택한다.)
첫 번째 열과 두 번째 열의 숫자만 유효하고 뒤에 있는 것은 마음대로 배열할 수 있다는 것을 쉽게 생각할 수 있다.그리고 1열의 서열을 이렇게 배열해야 한다고 생각하기 쉽다. 관건은 2열이 어떻게 해야 하는가이다.








.
.
여기에는 세 가지 상황으로 나뉘어 토론하는데 n==m일 때 두 번째 열은 마음대로 선택한다.
n>m일 때, 두 번째 열은 모두 n번 서버를 선택합니다.
n#include<cstdio> #include<iostream> #include<algorithm> #include<map> #include<vector> #include<cstring> #include<set> #include<utility> using namespace std; int a[105][105]; int vis[105][105]; int main() { int st,n,m; // for(n=2;n<=100;n++) //debug // for(m=1;m<=100;m++) while(cin>>n>>m) { memset(vis,0,sizeof(vis));st=2; for(int i=1,c=0;i<=m;c++,i++) { a[i][1]=c%n+1; vis[i][a[i][1]]=1; } if(n>m) { st=3; for(int i=1;i<=m;i++) a[i][2]=n,vis[i][n]=1; } else if(n<m) { st=3; int t=n; for(int i=1;i<=m;i++) { a[i][2]=t; if(i%(n-1)==0) t=(t-1)?t-1:n; vis[i][a[i][2]]=1; } } for(int i=1;i<=m;i++) for(int j=1,t=st;j<=n;j++) if(!vis[i][j]) a[i][t++]=j; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++) if(j==1) printf("%d",a[i][j]); else printf(" %d",a[i][j]); puts(""); } } return 0; }
void debug()
{
    int ans=0;
    for(int i=1;i<=n;i++){int sum[105]={0};
        for(int j=1;j<=m;j++)
            if(a[j][1]==i) sum[a[j][2]]++;
            else sum[a[j][1]]++;
    int mins=99999,maxs=-1;
    for(int kk=1;kk<=n;kk++) if(kk!=i)mins=min(mins,sum[kk]),maxs=max(maxs,sum[kk]);
    ans=max(maxs-mins,ans);
    }
    printf("%d %d %s
",n,m,ans<=1?"yes":"no"); if(ans>1) system("pause"); }

좋은 웹페이지 즐겨찾기