optim.cpp (3930B)
1 #include <vector> 2 #include <cstdio> 3 #include <algorithm> 4 #include <map> 5 6 using namespace std; 7 8 #define MAXN 1002 9 10 typedef pair<int,int> pii; 11 typedef pair<int,pii> piii; 12 13 struct Server{ 14 int id, z, c; 15 Server(int id=0, int z=0, int c=0) : id(id), z(z), c(c) {} 16 bool operator< (const Server &s) const{ 17 if (z*s.c == s.z*c) return z < s.z; 18 return z*s.c < s.z*c; 19 } 20 }; 21 22 struct comp{ 23 bool operator() (const Server &a, const Server &b){ 24 return a.z < b.z; 25 } 26 }; 27 28 int main() { 29 int R, S, U, P, M; 30 vector<Server> serv; 31 char grid[MAXN][MAXN]; // row, col 32 int capa[MAXN]; 33 int gcapa[MAXN][MAXN]; // row, group 34 int fposr[MAXN], fposc[MAXN], fgroup[MAXN]; 35 36 scanf("%d", &R); 37 scanf("%d", &S); 38 scanf("%d", &U); 39 scanf("%d", &P); 40 scanf("%d", &M); 41 for (int i = 0; i < U; i++) { 42 int r, s; 43 scanf("%d", &r); 44 scanf("%d", &s); 45 grid[r][s] = 1; 46 } 47 for (int i = 0; i < M; i++) { 48 int z, c; 49 scanf("%d", &z); 50 scanf("%d", &c); 51 serv.push_back(Server(i, z, c)); 52 } 53 54 for (int i = 0; i < M; i++) { 55 fposr[i] = fposc[i] = fgroup[i] = -1; 56 } 57 58 //read solution 59 for(int i = 0; i < M; i++) 60 { 61 int ar, as, ap; 62 scanf("%d", &ar);//'x' remplacé par -1 63 if(ar != -1) 64 { 65 fposr[i] = ar; 66 scanf("%d%d", &fposc[i], &fgroup[i]); 67 } 68 } 69 70 /* sort(serv.begin(), serv.end()); 71 72 // now keep only the servers we will use 73 int free = R * S - U; 74 75 int i; 76 for (i = 0; i < M; i++) { 77 free -= serv[i].c; 78 if (free <= 0) 79 break; 80 } 81 82 sort(serv.begin(), serv.begin() + i, comp()); 83 84 for (int i = 0; i < M; i++) { 85 fposr[i] = fposc[i] = fgroup[i] = -1; 86 } 87 88 for (int i = 0; i < M; i++) { 89 // place server i 90 // choose the group with lowest guaranteed 91 int guar[MAXN]; 92 for (int j = 0; j < P; j++) 93 guar[j] = capa[j]; 94 for (int j = 0; j < R; j++) 95 for (int k = 0; k < P; k++) 96 guar[k] = min(guar[k], capa[k] - gcapa[j][k]); 97 int mguar = guar[0], idx = 0; 98 for (int j = 0; j < P; j++) 99 if (guar[j] < mguar) { 100 mguar = guar[j]; 101 idx = j; 102 } 103 // idx is the group 104 // choose where to place server 105 vector<pii> v; 106 int wherecol = -1, whererow = -1; 107 for (int j = 0; j < R; j++) 108 v.push_back(make_pair<int, int>(gcapa[j][idx], j)); 109 sort(v.begin(), v.end()); 110 for (int j = 0; j < R; j++) { 111 // try to place in row 112 int row = v[j].second; 113 int contig = 0; 114 int k; 115 for (k = 0; k < S; k++) { 116 if (!grid[row][k]) 117 contig++; 118 else 119 contig = 0; 120 if (contig == serv[i].z) { 121 // ok, can place 122 break; 123 } 124 } 125 if (contig == serv[i].z) { 126 // do place 127 wherecol = k - (serv[i].z - 1); 128 whererow = row; 129 break; 130 } 131 } 132 if (wherecol >= 0 && whererow >= 0) { 133 // yeah, we can place it! update 134 capa[idx] += serv[i].c; 135 gcapa[whererow][idx] += serv[i].c; 136 for (int k = 0; k < serv[i].z; k++) 137 grid[whererow][wherecol+k] = 2; 138 fposr[serv[i].id] = whererow; 139 fposc[serv[i].id] = wherecol; 140 fgroup[serv[i].id] = idx; 141 } else { 142 printf("CANNOT PLACE!!\n"); 143 } 144 } 145 */ 146 147 148 int fguar[MAXN]; 149 for (int j = 0; j < P; j++) 150 fguar[j] = capa[j]; 151 for (int j = 0; j < R; j++) 152 for (int k = 0; k < P; k++) 153 fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]); 154 int mfguar = fguar[0], idx = 0; 155 for (int j = 0; j < P; j++) 156 if (fguar[j] < mfguar) { 157 mfguar = fguar[j]; 158 } 159 160 printf("FINAL: %d\n", mfguar); 161 162 for (int i = 0; i < R; i++) { 163 for (int j = 0; j < S; j++) 164 putchar(grid[i][j] == 1? 'X' : (grid[i][j] == 2 ? 'O' : ' ')); 165 putchar('\n'); 166 } 167 168 printf("CUT\n"); 169 170 // display sol 171 for (int i= 0 ; i < M; i++) { 172 if (fposr[i] >= 0) 173 printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]); 174 else 175 printf("x\n"); 176 } 177 178 return 0; 179 } 180