{"id":21,"date":"2013-03-01T13:46:01","date_gmt":"2013-03-01T05:46:01","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=21"},"modified":"2013-03-01T13:46:01","modified_gmt":"2013-03-01T05:46:01","slug":"1041-be-unique-20","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=21","title":{"rendered":"1041. Be Unique (20)"},"content":{"rendered":"

\u4e00\u9053\u96be\u9898\uff1f\u4e3b\u8981\u662f\u6728\u6709\u65b9\u6cd5\u3002<\/p>\n

1041. Be Unique (20)<\/h1>\n
\n
\n
\u65f6\u95f4\u9650\u5236\u00a0\u00a0<\/span><\/strong><\/div>\n
20 ms<\/span><\/strong><\/div>\n<\/div>\n
\n
\u5185\u5b58\u9650\u5236<\/div>\n
32000 kB<\/div>\n<\/div>\n
\n
\u4ee3\u7801\u957f\u5ea6\u9650\u5236<\/div>\n
16000 B<\/div>\n<\/div>\n
\n
\u5224\u9898\u7a0b\u5e8f<\/div>\n
Standard<\/div>\n<\/div>\n
\u4f5c\u8005<\/div>\n
CHEN, Yue<\/div>\n<\/div>\n
\nBeing unique is so important to people on Mars that even their lottery is designed in a unique way.\u00a0 The rule of winning is simple: one bets on a number chosen from [1, 104<\/sup>].\u00a0 The first one who bets on a unique number wins.\u00a0 For example, if there are 7 people betting on 5 31 5 88 67 88 17, then the second one who bets on 31 wins.
\n Input Specification: <\/b>
\nEach input file contains one test case.\u00a0 Each case contains a line which begins with a positive integer N (<=105<\/sup>) and then followed by N bets.\u00a0 The numbers are separated by a space.
\n Output Specification: <\/b>
\nFor each test case, print the winning number in a line.\u00a0 If there is no winner, print “None” instead.
\nSample Input 1:<\/b><\/p>\n
7 5 31 5 88 67 88 17<\/pre>\n
Sample Output 1:<\/b><\/p>\n
31<\/pre>\n
Sample Input 2:<\/b><\/p>\n
5 888 666 666 888 888<\/pre>\n
Sample Output 2:<\/b><\/p>\n
None<\/pre>\n<\/div>\n
\u672c\u4eba\u89e3\u7b54\uff1a<\/p>\n
\n\/\/#include \n\/\/#include \n#include \n#include \nusing namespace std;\nconst int MAX_NUM_A = 10001;\n\/\/const int MAX_NUM_B = 10000;\nint storage[MAX_NUM_A] = {0};\n\/\/list possibles;\nint possibles[MAX_NUM_A] = {0};\n\/\/0\u4ee3\u8868\u5c1a\u672a\u5b58\u50a8\uff0c-1\u4ee3\u8868\u5df2\u7ecf\u8d85\u989d\uff0c\u5176\u4f59\u4ee3\u8868\u8f93\u5165\u65f6\u7684\u987a\u5e8f\uff08\u7b2c\u51e0\u4e2a\u8f93\u5165\u7684\u8fd9\u4e2a\u6570\uff09\n\/\/int sequence[MAX_NUM_B];\n\/\/list ary_list;\n\/*\ninline void remove(int r)\n{\n\t\/\/remove item from array\n\tary_list.remove(r);\n}\n*\/\nint main()\n{\n\tclock_t  clockBegin, clockMid, clockEnd;\n\tint possibleN = 0;\n\tint N;\n\t\/\/cin >> N;\n\tscanf(\"%u\",&N);\n\tint input;\n\tclockBegin = clock();\n\tfor (int i=0; i> input;\n\t\tscanf(\"%u\", &input);\n\t\tif(storage[input] == 0)\n\t\t{\n\t\t\t\/\/\u5c1a\u672a\u8f93\u5165\u8fc7\u8fd9\u4e2a\u6570\n\t\t\tstorage[input] = i+1; \/\/\u8bb0\u5f55\u8f93\u5165\u7684\u987a\u5e8f\n\t\t\t\/\/possibleN ++;\n\t\t\t\/\/possibles.push_back(input);\n\t\t\tpossibles[possibleN++] = input;\n\t\t}\n\t\telse\n\t\t{\n\t\t\t\/\/\u91cd\u590d\u4e86\uff01\n\t\t\t\/\/if(storage[input] > 0)\n\t\t\t\/\/{\n\t\t\t\t\/\/possibles.remove(input);\n\t\t\t\t\/\/possibleN --;\n\t\t\t\/\/}\n\t\t\tstorage[input] = -1;\n\t\t}\n\t}\n\t\/*\n\tif(possibles.size() <= 0)\n\t{\n\t\tcout << \"None\";\n\t\treturn 0;\n\t}\n\t*\/\n\tclockMid = clock();\n\t\/\/cout << clockMid - clockBegin << endl;\n\tprintf(\"%un\",clockMid - clockBegin);\n\t\/\/int count = ary_list.size();\n\tint min_seq = MAX_NUM_A;\n\tint min_val = -1;\n\tint i=0;\n\twhile(i < possibleN)\n\t{\n\t\tint temp = storage[possibles[i]];\n\t\tif(temp > 0)\n\t\t{\n\t\t\t\/\/if(temp < min_seq)\n\t\t\t\/\/{\n\t\t\t\tmin_seq = temp;\n\t\t\t\tmin_val = possibles[i];\n\t\t\t\tbreak;\n\t\t\t\/\/}\n\t\t}\n\t\t\/\/possibles.pop_front();\n\t\ti ++ ;\n\t}\n\tclockEnd = clock();\n\t\/\/cout << clockEnd - clockMid << endl;\n\tprintf(\"%un\",clockEnd - clockMid);\n\tif(min_val != -1)\n\t{\n\t\t\/\/cout << min_val;\n\t\tprintf(\"%u\",min_val);\n\t\treturn 0;\n\t}\n\t\/\/cout << \"None\";\n\tprintf(\"None\");\n\treturn 0;\n}\n<\/pre>\n
\u77e5\u9053\u7ed3\u8bba\u662f\u4ec0\u4e48\u4e48\uff1f
\n\u7ed3\u8bba\u662fsscan\u6bd4cin\u6548\u7387\u9ad8\u5f88\u591a\uff01<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u9053\u96be\u9898\uff1f\u4e3b\u8981\u662f\u6728\u6709\u65b9\u6cd5\u3002 1041. Be Unique (20) \u65f6\u95f4\u9650\u5236\u00a0\u00a0 20 ms \u5185\u5b58\u9650\u5236 32000 kB \u4ee3\u7801\u957f\u5ea6\u9650\u5236 16000 B \u5224\u9898\u7a0b\u5e8f Standard \u4f5c\u8005 CHEN, Yue Being unique is so important to people on Mars that even their lottery is designed in a unique way.\u00a0 The rule of winning is simple: one bets on a number chosen from [1, 104].\u00a0 The first […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-21","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/21","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=21"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/21\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=21"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=21"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=21"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}