BOJ 18891 - 제21대 국회의원 선거

BOJ 18891 - 제21대 국회의원 선거

비문학 지문같은 문제이다.

열심히 지문을 읽고 적당하게 이해한다음에 구현을 해주어야 한다.

큰 힌트는 구현할 때 의구심이 들었던 실수오차에 대해서는 그냥 double 을 써줘도 문제가 없다는 것이다.

struct party {
   string name;
   int r, voted, sprime, s, t;
   bool have_sit;
   double p, x, tx;
};

void solve() {
   int P, V;
   cin >> P >> V;
   vector<party> p(P);

   int valid_vote = 0;
   for (int i = 0; i < P; i++) {
      cin >> p[i].name >> p[i].r >> p[i].voted;
      if (p[i].r >= 5) p[i].have_sit = p[i].r >= 5;
      valid_vote += p[i].voted;
   }
   for (int i = 0; i < P; i++) if (p[i].voted * 100 >= valid_vote * 3) p[i].have_sit = 1;
   valid_vote = 0;
   for (int i = 0; i < P; i++) if (p[i].have_sit) valid_vote += p[i].voted;

   for (int i = 0; i < P; i++) {
      if (p[i].have_sit) {
         p[i].p = 1.0 * p[i].voted / valid_vote;
      }
   }
   auto musosok = [&]() {
      int ret = 300 - 47;
      for (int i = 0; i < P; i++) ret -= p[i].r;
      return ret;
   };
   debug(musosok());
   int R = musosok();
   for (int i = 0; i < P; i++) if (!p[i].have_sit) R += p[i].r;

   int sprime_sum = 0;
   for (int i = 0; i < P; i++) {
      if (p[i].have_sit) {

         double tmp = ((300.0 - R) * p[i].p - p[i].r) / 2.0;
         tmp = tmp < 1 ? 0 : round(tmp);

         int sprime = max(0ll, int(tmp));
         p[i].sprime = sprime;
         sprime_sum += sprime;
      }
   }
   if (sprime_sum == 30) {
      for (int i = 0; i < P; i++) p[i].s = p[i].sprime;
   } else if (sprime_sum < 30) {

      for (int i = 0; i < P; i++) {
         double x = p[i].sprime + (30 - sprime_sum) * p[i].p;
         int xn = x;
         x -= xn;
         p[i].x = x;
         p[i].s = xn;
      }
      int s_sum = 0;
      for (int i = 0; i < P; i++) if (p[i].have_sit) s_sum += p[i].s;
      while (s_sum < 30) {
         int mx_idx = -1;
         double mx_value = -1;
         for (int i = 0; i < P; i++) if (p[i].have_sit) if (p[i].x > mx_value) { mx_value = p[i].x, mx_idx = i; }
         assert(~mx_idx);
         p[mx_idx].s++;
         p[mx_idx].x = -1;
         s_sum++;
      }

   } else if (sprime_sum > 30) {
      for (int i = 0; i < P; i++) {
         double x = (30.0 * p[i].sprime) / sprime_sum;
         int xn = x;
         x -= xn;
         p[i].x = x;
         p[i].s = xn;
      }
      int s_sum = 0;
      for (int i = 0; i < P; i++) if (p[i].have_sit) s_sum += p[i].s;
      while (s_sum < 30) {
         int mx_idx = -1;
         double mx_value = -1;
         for (int i = 0; i < P; i++) if (p[i].have_sit) if (p[i].x > mx_value) { mx_value = p[i].x, mx_idx = i; }
         assert(~mx_idx);
         p[mx_idx].s++;
         p[mx_idx].x = -1;
         s_sum++;
      }
   }
   for (int i = 0; i < P; i++) {
      debug(p[i].name, p[i].sprime, p[i].s);
   }
   int t_sum = 0;
   for (int i = 0; i < P; i++) {
      double cur_t = 17 * p[i].p;
      p[i].t += int(cur_t);
      cur_t -= p[i].t;
      p[i].tx = cur_t;
      t_sum += p[i].t;
   }
   while (t_sum < 17) {
      int mx_idx = -1;
      double mx_value = -1;
      for (int i = 0; i < P; i++) if (p[i].have_sit) if (p[i].tx > mx_value) { mx_value = p[i].tx, mx_idx = i; }
      assert(~mx_idx);
      p[mx_idx].t++;
      p[mx_idx].tx = -1;
      t_sum++;
   }

   vi idx(P);
   iota(all(idx), 0);
   sort(all(idx), [&](int i, int j) {
      int a = p[i].s + p[i].t + p[i].r;
      int b = p[j].s + p[j].t + p[j].r;
      if (a ^ b) return a > b;
      return p[i].name < p[j].name;
   });
   for (int i: idx) {
      cout << p[i].name << ' ' << p[i].s + p[i].t + p[i].r << endl;
   }
}