web analytics

NOIP2013 Day1 火柴排序

题目链接: 随便找一个OJ应该都有吧.QAQ嘤嘤嘤.

分析:

考试拿到数学公式都应该去拆分一下QwQ. 这样可能对解题有帮助>_<

所以我们分析一下这个价值的计算式

 \sum_{i=1}^{n} (a_i - b_i)^2 = \sum_{i=1}^{n} (a_i^2+b_i^2 - 2 \cdot a_i \cdot b_i)

因为 a_i  b_i 都是定值所以我们的值就取决于\sum_{i=1}^{n}( a_i \cdot b_i)

证明:

若存在a>b,c>d,且ac+bd<ad+bc,则a(cd)<b(cd),a<b,与a>b矛盾,所以若a>b,c>d,则ac+bd>ad+bc

 

所以我们只有正序才能保证最优解.

 

所以我们移动只需要固定一个序列.然后用另一个序列的位置.去匹配就好.

交换的次数就是逆序对的数量.

 

 

 

36 Trackbacks

  1. By puma sneakers mens sale pinterest.com on 十一月 10, 2018 at 3:55 上午

    puma sneakers mens sale pinterest.com

    adidas zx racer white bluemens lebron james 13 xiii low pe jr smith playoff cavs black yellow rednike air force 1 low logos pack black release date ah8462 1002018 girls air jordan 12 gs heiress plum fog for sale

  2. By ua curry one 1 sc30 away underdog dark gray crimson on 十一月 11, 2018 at 11:26 上午

    ua curry one 1 sc30 away underdog dark gray crimson

    mens san francisco giants majestic gray road on-field 60th season patch flex base custom jerseynike limited justin hardy 14 atlanta falcons jerseymens minnesota twins byung-ho park majestic scarlet alternate cool base player jerseymens milwaukee brewer…

  3. By crystal vans off the wall canvas on 十一月 11, 2018 at 4:07 下午

    crystal vans off the wall canvas

    noir violet nike eric koston 2 maxblanc vans x disneyorange blanc converse one starjaune rouge jordan fly 89

  4. male golden state warriors 11 klay thompson black short sleeve new swingman jersey

    mens chicago blackhawks ccm red 2016 alumni stadium series team premier jerseygame darryl roberts 27 new york jets jerseykids antonio hamilton 32 oakland raiders jerseypro line sean culkin 80 los angeles chargers jersey

  5. By off white x nike air force 1 low 596728 919 on 十一月 11, 2018 at 9:31 下午

    off white x nike air force 1 low 596728 919

    throwback lance lenoir 14 dallas cowboys jerseypro line datone jones 56 dallas cowboys jerseymens jacksonville jaguars andrew norwell nfl pro line black player jerseygolden state warriors 1 javale mcgee 2016 17 white home jersey

  6. jordan hydro 6 synthetic massage slippers 881474 101 white black red

    nike air jordan 13 retro bred black varsity red whiteadidas nemeziz messi 17.3 fg cp9038black blue orange mens lebron james 13 low2018 new jordan shoes cheap air jordan 5 bronze 819171 417

  7. By big tall detrez newsome 38 los angeles chargers jersey on 十一月 12, 2018 at 8:08 上午

    big tall detrez newsome 38 los angeles chargers jersey

    womens nike limited oakland raiders custom jerseymens christian westerman 63 cincinnati bengals jerseylegend dede westbrook 12 jacksonville jaguars jerseymens cole hikutini 83 san francisco 49ers jersey

  8. By nike kobe nxt black on 十一月 12, 2018 at 8:31 下午

    nike kobe nxt black

    nike air force 1 mid supremereg; nba blackall blue jordan 12 pinterest.comgold and diamond watch pinterest.compolo factory outlet shop online pinterest.com

  9. By grey and blue lebrons on 十一月 13, 2018 at 4:22 下午

    grey and blue lebrons

    stephen curry 1 dubnationpuma soccer glovesnew jordan shoes for kidsretro 12 dynamic pink

  10. By auto lacing twitter.com on 十一月 13, 2018 at 5:54 下午

    auto lacing twitter.com

    cute lingerie pinterest.comkobe 11 shoe names pinterest.comall white vans mens pinterest.comvans denim chevron authentic womens shoes

  11. By kdvi lam cameo uk trainers on 十一月 14, 2018 at 7:14 上午

    kdvi lam cameo uk trainers

    adidas predator bamboo light loden uk trainersnike roshe run hyp qs 3m eel yellow uk trainersconverse all star princess canvas bleached lilac uk trainersvans era 59 rosse uk trainers

  12. By air jordan mens air jordan 9 on 十一月 15, 2018 at 5:22 下午

    air jordan mens air jordan 9

    puma puma fentyadidas nmd adidas nmd xr1nike air max nike air vapormax 2018adidas ultra boost adidas ultra boost 40

  13. By 864347 800 nike sb zoom blazer low vintage coral on 十一月 15, 2018 at 7:29 下午

    864347 800 nike sb zoom blazer low vintage coral

    adidas ultra boost uncaged blue white ba9616 mensnike lebron 14 low khakiair jordan 2 ii converse fastbreak pack the 2 that started it allnike air max 95 premium light bone string

  14. By schwarz volt adidas nmd boost on 十一月 15, 2018 at 9:37 下午

    schwarz volt adidas nmd boost

    adidas originals 350 spezial mens trainers shoes white sports sneakersadidas originals sl 72nike air max 90 ultra 2.0 flyknit hyper turquoise white 875943 301 mens sz 11kd vi olympic

  15. By mens free shoes nike free tr fit 2 on 十一月 17, 2018 at 8:43 下午

    mens free shoes nike free tr fit 2

    nike free mens nike free run 3nike roshe run nike roshe run floral swooshnike air huarache nike air huarache nm womensnike free womens nike free 50 v4

  16. By bleu vert blanc new balance nb580 on 十一月 19, 2018 at 1:34 下午

    bleu vert blanc new balance nb580

    2014 nike pike greyadidas predator absolado instinct ag footwear whiteadidas nmd xr1 sparklenike air entertrainer pinterest

  17. By adidas new adidas nemeziz on 十一月 20, 2018 at 1:07 下午

    adidas new adidas nemeziz

    "womens air force 1 nike air force 1 midwomens air force 1 nike air force 1 lownike air force 1 ultra flyknit nike air force 1 ultra flyknit lownike air force 1 ultra flyknit"

  18. By 褋械褉褘泄 芯褉邪薪卸械胁褘泄 new balance 999 on 十一月 21, 2018 at 7:28 下午

    褋械褉褘泄 芯褉邪薪卸械胁褘泄 new balance 999

    noir rouge kobe 4noir marron air jordan xviijaune rose converse youth graduation seasonargent bleu nike zoom stefan janoski

  19. By voltio p煤rpura nike kaishi 2.0 on 十一月 21, 2018 at 11:48 下午

    voltio p煤rpura nike kaishi 2.0

    marr贸n naranja nike mercurial vapor xi fgazul plata 2012 adidasblanco oro puma sude platfotmoro armada d rose 7 low

  20. By uk trainers converse all star hi chuck 100 gum on 十一月 22, 2018 at 10:16 上午

    uk trainers converse all star hi chuck 100 gum

    uk trainers grade school nike tiempo diamond blinguk trainers nike solarsoft kd slide black white reduk trainers womens asics tiger coolidge lo custom sparkleuk trainers womens nike air zoom vomero v13 brown

  21. By rot silber adidas superstar 360 summer kind on 十一月 22, 2018 at 1:28 下午

    rot silber adidas superstar 360 summer kind

    gr眉n gr眉n jordan 18khaki schwarz adidas ace 17.3beige grau new balance nb996vlpmarine merrell proterra sport gtx

  22. By plata rosado nike hyperadapt 1.0 on 十一月 23, 2018 at 6:03 下午

    plata rosado nike hyperadapt 1.0

    armada negro nike air zoom vomero v13negro rojo adidas copa 17.1 fggris rojo air jordan 2017armada rosado converse cowboy

  23. By rose kaki rouge puma suede rihanna on 十一月 24, 2018 at 5:04 上午

    rose kaki rouge puma suede rihanna

    adidas nmd city sock blueadidas x 17.4 turquoisenike ambassador 9 raw whiteboys girls shoes bleached lilac

  24. By adidas lillard 2 colorways on 十一月 25, 2018 at 1:54 下午

    adidas lillard 2 colorways

    nike flyknit free run sale twitter.comnew balance 998 made in usa youtube.comadidas stan smith mens 9.5 tumblr.comasics goes 50 50 with new summer releases

  25. By uk trainers womens puma rihanna 2018 black white red on 十一月 25, 2018 at 3:14 下午

    uk trainers womens puma rihanna 2018 black white red

    lilla hvid kvinders vans backpackorange s酶lv nike air zoom vomero 13bl氓 r酶d nike sunray adjustablebrun s酶lv virgilabloh

  26. By khaki schwarz adidas copa on 十一月 29, 2018 at 7:26 上午

    khaki schwarz adidas copa

    gr眉n gold nike mercurial superfly v fgsilber schwarz nike comfort slidewei脽 gr眉n jordan 19wei脽 volt herren nike shox r3

  27. By nike 90 youtube.com on 十二月 3, 2018 at 7:47 下午

    nike 90 youtube.com

    air jordan flight salmonadidas prophere artisan tealpuma carson mesh polar aluminumpuma carson mesh polar aluminum

  28. By derrick rose black and white shoes co.uk on 十二月 7, 2018 at 1:22 下午

    derrick rose black and white shoes co.uk

    uk trainers vans era rioja reduk trainers nike free hypervenom 3 bronzyuk trainers nike air max ld zero soft reduk trainers nike free hypervenom 3 bronzy

  29. By asics asics n20 on 十二月 13, 2018 at 8:48 上午

    asics asics n20

    adidas zx 710adidas zx 710 adidas zx 710 mensnike air pegasus 89nike air pegasus 89 nike air pegasus 89 mens

  30. By 卸械谢褌褘泄 褋懈薪懈泄 puma tsugi on 十二月 13, 2018 at 2:39 下午

    卸械谢褌褘泄 褋懈薪懈泄 puma tsugi

    fenty shoes white tumblr.comfenty shoes white tumblr.comvans leather era wingtipvans leather era wingtip

  31. vests womens the north face pseudio vest medium grey heather gift live

    nike down filled parka jacket blackwomens nike navy los angeles rams champ drive boyfriend pullover sweatshirtrib cuff pants championchampion womens smoothtec capri legging black

  32. By nba jordan shoes air jordan super fly on 十二月 14, 2018 at 7:44 下午

    nba jordan shoes air jordan super fly

    nike legacy 91nike air max excelle rappe 4nike sunray adjustapple watch

  33. nike free 4.0 v3 ext suede mens black light grey shoes nike running shoes black nike running

    extra wide shoesmens athletic shoes salomon detroitblack navajohoodies sweatshirts tags puma puma big boys zipadidas derrick rose

  34. nike mercurial vapor superfly iii fg soccer cleats blue white united statesnike free woven

    wdywtwdywt asics gel lyte v sage flamingo lacespink supras vaider baby shoesboys grade school reebok zjet thunder shoes greyblackbarato zapatillas mujer supra cuttler ns neon max gris de ne de

  35. By naranja naranja converse true love graffiti on 十二月 15, 2018 at 7:16 下午

    naranja naranja converse true love graffiti

    amarillo negro mbt kabisa 5rosado negro puma classic sneakersblanco naranja nike air icarus extrarojo gris asics gel kinsei 6

  36. By 卸械谢褌褘泄 褔械褉薪褘泄 adidas cc fresh 2 on 十二月 16, 2018 at 8:34 下午

    卸械谢褌褘泄 褔械褉薪褘泄 adidas cc fresh 2

    锌褍褉锌褍褉薪褘泄 芯褉邪薪卸械胁褘泄 air jordan son of mars蟹芯谢芯褌芯 卸械谢褌褘泄 suicoke black kisee v sandals泻芯褉懈褔薪械胁褘泄 蟹芯谢芯褌芯 puma suede luhan low芯褉邪薪卸械胁褘泄 褋懈薪懈泄 adidas sobakov

Post a Comment

You must be logged in to post a comment.