Mamy ciąg $n$ par liczb $(a_i,b_i)$. Zadanie sprowadza się do wybrania takich dwóch podzbiorów $A, B \subseteq \{1,\ldots,n\}$, które maksymalizują wartość $$\min\Big(\sum_{i\in A} a_i,\ \sum_{i\in B} b_i\Big) - |A| - |B|.$$

Rozwiązanie kwadratowe

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));
    }
  }