首页 > 代码库 > codechef - Discrepancies in the Voters List 题解
codechef - Discrepancies in the Voters List 题解
codechef的本题算法也不难,但是codechef喜欢大数据,动不动就过万过十万,输入输出处理不好就会超时。
就像本题最大数据可能达到15万个整数。普通输入输出铁定超时了。
这里使用fread和fwrite这两个函数,设置好buffer,速度还是相当快的,而且相对很多程序都比较简单的了。
主要注意:
每个buffer数据块和下一个buffer数据块之间的衔接,不能破坏了最终需要的格式,也不要在输入的时候破坏了数据连续性。
很低层的东西了,不过用多久慢慢熟悉了。
题意就是:找出三个数列中的所有在两个数列都出现的数值。
原题:http://www.codechef.com/problems/VOTERS/
处理算法的代码还不到输入输出代码的一半呢。
#pragma once #include <utility> #include <algorithm> #include <assert.h> #include <string> #include <stdio.h> #include <math.h> #include <iostream> using namespace std; int DiscrepanciesintheVotersList() { int N1, N2, N3, n = 0; scanf("%d %d %d\n", &N1, &N2, &N3); int *A = new int[N1]; int *B = new int[N2]; int *C = new int[N3]; char buffer[10000]; int num = 0, id = 0, i = 0, j = 0, k = 0; while ((n = fread(buffer, 1, 10000, stdin)) > 0) { for (int i = 0; i < n; i++) { if (‘0‘ <= buffer[i] && buffer[i] <= ‘9‘)//避免有空格 { num = num * 10 + (buffer[i] - ‘0‘); } else if (buffer[i] == ‘\n‘) { if (j < N1) A[j] = num; else if (j < N1+N2) B[j-N1] = num; else C[j-N1-N2] = num; j++; num = 0; } } } if (0 != num) C[N3-1] = num;//需要额外处理一个数据,不能在循环中处理 int newN = max(N1, max(N2, N3)); int *D = new int[newN]; id = 0, i = 0, j = 0, k = 0; while (i < N1 || j < N2 || k < N3) { int t = (1<<29); if (i < N1) t = min(t, A[i]); if (j < N2) t = min(t, B[j]); if (k < N3) t = min(t, C[k]); int c = 0; if (i < N1 && t == A[i]) c++, i++; if (j < N2 && t == B[j]) c++, j++; if (k < N3 && t == C[k]) c++, k++; if (c > 1) D[id++] = t; } printf("%d\n", id); for (int i = 0; i < id; ) { int j = 0; while (j < 9500 && i < id)//这里j要小于最大buffer 10000 { int sum = 0, tmp = D[i], st = j; while (tmp) { sum = tmp % 10; tmp /= 10; buffer[j++] = sum + ‘0‘; } reverse(buffer+st, buffer+j); buffer[j++] = ‘\n‘; i++; } fwrite(buffer, 1, j, stdout); //每次都需要多打个‘\n‘,因为数据可能大于当次的buffer } delete []A; delete []B; delete []C; delete []D; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。