Jeśli ustalimy rozmiary podzbiorów $A$ i $B$ , to widać, że możemy je wybierać niezależnie od siebie. Zatem opłaca się, żeby w $A$ znajdowało się $| A |$ największych wartości $a_{i}$ , analogicznie w $B$ chcemy mieć $| B |$ największych wartości $b_{i}$ .

Możemy zatem najpierw posortować listy, zrobić dla nich sumy prefiksowe, a następnie przeiterować się w czasie $O (n^{2})$ po wszystkich wyborach rozmiarów podzbiorów $A$ i $B$ :

const int N = 110000;
int n;
double a[N],b[N];
double pa[N],pb[N];

int main() {
  scanf("%d",&n);
  REP(i,n) scanf("%lf%lf",&a[i],&b[i]);

  sort(a,a+n,greater<double>());
  sort(b,b+n,greater<double>());

  REP(i,n) pa[i+1] = pa[i] + a[i];
  REP(i,n) pb[i+1] = pb[i] + b[i];

  double ans = 0;
  REP(an,n+1) REP(bn,n+1) {
    double cost = min(pa[an], pb[bn]) - (an + bn);
    ans = max(ans, cost);
  }

  printf("%.4lf\n", ans);
}

Rozwiązanie wzorcowe

Zobaczmy, jak może się realizować minimum $M = min (\sum_{i \in A} a_{i}, \sum_{i \in B} b_{i})$ . Jeśli jest $M = \sum_{i \in A} a_{i}$ dla pewnego $i$ , to mamy $n + 1$ kandydatów na tę wartość. Co więcej, musimy tak dobrać rozmiar zbioru $B$ , żeby $M \leq \sum_{i \in B} b_{i}$ . Oczywiście, najlepiej jest wybrać jak najmniejszy taki zbiór (żeby zminimalizować $| B |$ ), więc możemy go po prostu wyszukać binarnie.

Tak więc obsługa tych przypadków zajmie czas $O (n \log n)$ . Symetrycznie rozważamy przypadek, gdy $M = \sum_{i \in B} b_{i}$ dla pewnego $i$ :

  REP(an,n+1) {
    int bn = lower_bound(pb, pb+n+1, pa[an]) - pb;
    if (bn <= n) {
      ans = max(ans, pa[an] - (an + bn));
    }
  }
  REP(bn,n+1) {
    int an = lower_bound(pa, pa+n+1, pb[bn]) - pa;
    if (an <= n) {
      ans = max(ans, pb[bn] - (an + bn));
    }
  }