I'm trying to solve this problem with a greedy approach, first assign the number of students assigned to each classroom as to maximize the number of possible pairs. Then make sure that I have chosen a pair for each of them, and then just choose enough available pairs to complete the ones asked. However, I'm getting WA in test case 7, any idea of why this approach fails?
Now AC, my initial assignment was failing. For example: 10 3 5. Thanks to aropan.
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
int n,k,m;
scanf("%d %d %d",&n,&k,&m);
int cont[100];
for(int i = 0,x = n/k;i < m;++i) cont[i] = x;
for(int i = n % k - 1;i >= 0;--i) ++cont[i];
int room[100];
for(int i = 0,k = 0;i < m;++i)
for(int j = 0;j < cont[i];++j)
room[k++] = i;
for(int i = 0;i < n;++i)
printf("%d\n",room[i] + 1);
bool M[100][100];
memset(M,false,sizeof(M));
for(int i = 0;i < n;++i)
for(int j = i + 1;j < n;++j)
M[i][j] = M[j][i] = (room[i] != room[j]);
bool used[100];
memset(used,false,sizeof(used));
for(int i = 0;i < n;++i){
if(!used[i]){
for(int j = 0;j < n;++j){
if(M[i][j] && !used[j]){
used[i] = true; used[j] = true;
M[i][j] = M[j][i] = false;
printf("%d %d\n",i + 1,j + 1);
--m;
break;
}
}
}
if(!used[i]){
for(int j = 0;j < n;++j){
if(M[i][j]){
used[i] = true;
M[i][j] = M[j][i] = false;
printf("%d %d\n",i + 1,j + 1);
--m;
break;
}
}
}
}
for(int i = 0;i < n && m > 0;++i){
for(int j = i + 1;j < n && m > 0;++j){
if(M[i][j]){
M[i][j] = M[j][i] = false;
printf("%d %d\n",i + 1,j + 1);
--m;
}
}
}
return 0;
}
Comments (3)
0
