Problem H
Färgglada smällar
Anita älskar färger och tycker att nyår är årets höjdpunkt. Hennes vän Julia kommer att skjuta upp $N$ fyverkerier på nyårsafton, och nu hon vill att Anita ska bevisa vilken bra vän hon är genom att titta på hennes fyverkerier. Det enda problemet är att Smällsällskapet också skjuter upp $N$ fyverkerier på nyårsafton, exakt samtidigt som Julias. Anita kommer alltid att titta på de fyverkerier som är färggladast och om fyrverkerierna är lika färgglada kommer hon att titta på Julias. Julia har bett Anita att välja vilken ordning hon ska skjuta upp sina fyverkerier i, och för att skjuta upp problemet med att hon inte är en tillräckligt bra vän vill Anita därför välja en ordning så att hon kan se så många av Julias fyverkerier som möjligt. Hur många av Julias fyverkerier kommer Anita att kunna titta på om hon väljer en så bra ordning som möjligt?
Indata
Första raden innehåller talet $N$ ($N \leq 100\, 000$), antalet fyrverkerier som Julia och Smällsällskapet kommer att skjuta upp vardera. Nästa rad innehåller $N$ stycken tal $J_1, \dots , J_ N$, där talet $J_ i$ ($1 \le J_ i \leq 10^9$) representerar hur färgglatt fyrverkeri $i$ av Julias fyrverkerier är. Därefter följer en rad med $N$ stycken tal $S_1, \dots , S_ N$, där talet $S_ i$ ($1 \le S_ i \leq 10^9$) representerar hur färgglatt fyrverkeri $i$ av Smällsällskapets fyrverkerier är.
Utdata
Skriv ut ett tal: hur många av Julias fyrverkerier som Anita maximalt kan titta på.
Poängsättning
Din lösning kommer att testas på en mängd olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
Grupp |
Poängvärde |
Begränsningar |
1 |
30 |
$N \leq 1000$ |
2 |
35 |
Både Anitas och Smällsällskapets fyrverkerier är sorterade i ökande ordning efter hur färgglada de är |
3 |
35 |
Inga ytterligare begränsningar |
Förklaring
I det första exempelfallet kan man skjuta upp Julias raketer i ordningen: 1, 3, 2. Då kommer alla raketer att vara lika färgglada som Smällsällskapets och Anita kommer att titta på alla tre.
I det andra exempelfallet kommer både Julias raketer som har färggladhet 4 och 5 att vara mer färgglada än Smällsällskapets första raket som har färggladhet 2. Exempelvis kan man skjuta upp Julias raketer i ordningen: 4, 5, 1 och då kommer Anita att kolla på den första.
I det tredje exempelfallet kan man exempelvis skjuta upp Julias raketer i ordningen 1, 3, 4, 2. Då kommer Anita att kolla på de tre första av Julias raketer.
Sample Input 1 | Sample Output 1 |
---|---|
3 2 1 3 1 3 2 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
3 1 4 5 2 8 10 |
1 |
Sample Input 3 | Sample Output 3 |
---|---|
4 2 1 4 3 3 4 1 5 |
3 |