12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 |
- #include "instance.h"
- using namespace std;
- int next(instance &ins) {
- int best = -1;
- for(int i = 0; i < ins.orders.size(); i++) {
- if(!ins.orders[i].ord.empty()) {
- best = i;
- break;
- }
- }
- return best;
- }
- void glouton(instance &ins) {
- vector<int> drone_temps(ins.drones);
- vector<pos> drone_pos;
- int score = 0;
- for(int i = 0; i < ins.drones; i++)
- drone_pos.push_back(ins.wh[0].p);
- while(true) {
- int next_i = next(ins);
- if(next_i < 0)
- break;
- int drone = rand()%ins.drones;
- order &ord = ins.orders[next_i];
- assert(!ord.ord.empty());
- pair<const int, int> &type = *ord.ord.begin();
- int quantity = min(type.second, ins.max_load/ins.weights[type.first]);
- int wa = ins.find(drone_pos[drone], type.first, quantity);
- quantity = min(quantity, ins.wh[wa].disp[type.first]);
- ins.wh[wa].disp[type.first] -= quantity;
- // decrease order / stock
- type.second -= quantity;
- if(!type.second)
- ord.ord.erase(type.first);
- // augment drone_temps
- drone_temps[drone] += 1+ceil(sqrt(drone_pos[drone].dist2(ins.wh[wa].p)));
- drone_temps[drone] += 1+ceil(sqrt(ins.wh[wa].p.dist2(ord.p)));
- drone_pos[drone] = ord.p;
- if(drone_temps[drone] > ins.T)
- break;
- // pass order
- cout << drone << " L " << wa << " " << type.first << " " << quantity << endl;
- cout << drone << " D " << next_i << " " << type.first << " " << quantity << endl;
- score += ceil(100.*(ins.T-drone_temps[drone])/ins.T);
- }
- cerr << "Score : " << score << endl;
- }
- int main() {
- int seed = time(NULL);
- srand(seed);
- cerr << "seed : " << seed << endl;
- instance ins;
- glouton(ins);
- return 0;
- }
|