| ||||||||||
| 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