Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
数据量大时候果然要注意输入的时间,用cin超时,改用gets就AC了参考了这位大牛的代码,多谢 http://poj.org/showmessage?message_id=171227 本来是很讨厌用scanf,gets和printf的,很不方便,很容易出错,但数据量大时候果然要注意输入的时间,用cin超时,改用gets就AC了 提交情况:同样的代码 用G++,984K,391MS 用C++,556K,297MS 看来还是C++快些 有几点注意: 1、输入时候将每行转换成整数,可以提前将字母到数字的映射存为数组,相当于hash。 最初是没有转换成整数,而是直接转换成长度为7的字符串,结果就超时了。 2、对于以000开头的输入,只要在输出的时候用0占位就可以了,如num是输出的号码,cnt是计数 printf("%03d-%04d %d", num / 10000, num % 10000, cnt) 3、计数的时候不用map,可以边输出边计数。也就是输出时间就是n。 下面是AC code: #include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; string map("2223334445556667#77888999#"); //ABCDEFGHIJKLMNOPQRSTUVWXYZ char s[40]; int convert(); // convert s to standard form s1 int main() { int n, cnt; scanf("%d", &n); getchar(); vector<int> ivec(n); for (int i = 0; i < n; i++) { gets(s); ivec[i] = convert(); } sort(ivec.begin(), ivec.end()); // output the result bool no_duplicate = true; for (int i = 1; i < n; i++) { cnt = 1; while (i < n && ivec[i] == ivec[i - 1]) { cnt++; i++; } if (cnt > 1) { printf("%03d-%04d %d\n", ivec[i-1]/10000, ivec[i-1]%10000, cnt); no_duplicate = false; } } if (no_duplicate) printf("No duplicates. \n"); return 0; } int convert() { int sum = 0; for (unsigned i = 0; s[i] != '\0'; i++) { if (s[i] >= '0' && s[i] <= '9') sum = sum * 10 + (s[i] - '0'); else if (s[i] >= 'A' && s[i] <= 'Z' && s[i] != 'Q' && s[i] != 'Z') sum = sum * 10 + (map[s[i] - 'A'] - '0'); } return sum; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator