| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 6 | 2 | 2 | 33.333% |
Fredrik har just ställt ut nya blommor på sin fönsterbräda. Men någonting känns lite fel. Det är inte riktigt så symmetriskt som han skulle vilja ha det.
Det finns $K$ olika blomsorter och varje sort beskrivs av ett av heltalen $1,2,...,K$. Fönsterbrädan har $N$ blommor utställda på rad från vänster till höger. Den $i$:te blomman från vänster är av sort $a_i$. Fredrik vill att blommorna ska vara symmetriska, d.v.s att $a_i=a_{N+1-i}$ gäller för alla $i$. För att åstakomma detta tänker han göra drag som byter plats på två intilliggande blommor. Ett drag kan alltså byta plats på blomma $i$ och blomma $i+1$ för något $1\le i \le N-1$.
Vad är minsta antalet drag som krävs för att uppnå blomsymmetri?
Den första raden av indata innehåller två heltal $N$ och $K$ ($1 \le N,K \le 200 000$): antalet blomor på fönsterbrädan och totala antalet sorter som finns. Därefter följer en rad med $N$ heltal $a_1,a_2,...,a_N$ ($1\le a_i \le K$): blommorna på fönsterbrädan.
Det garanteras att det finns en sekvens av drag som ordnar blommorna symmetriskt.
Skriv ut ett tal: det minsta möjliga antalet drag för att uppnå blomsymmetri.
4 5 5 5 2 2
2
8 3 3 1 1 1 2 3 1 2
5
7 3 1 3 2 1 2 2 2
5
I det första exemplet kan vi börja med att byta plats på blomma 2 och 3, och sedan på blomma 1 och 2. Då kommer blommorna hamna i ordningen 1 3 3 1.
I det andra exemplet kan vi till exempel göra följande 5 byten i ordning: 4 och 5, 3 och 4, 1 och 2, 2 och 3, 7 och 8. Då kommer blommorna hamna i ordningen 1 2 3 1 1 3 2 1.
Olympiad > Swedish Olympiad in Informatics > 2021 > KATT ?번