洛谷P2397摩尔投票法的优化

第一次提交的思路和代码是的你没有想错我是直接拿着上一篇解决2013年408的解法直接去提交洛谷P2397 yyy loves Maths VI (mode) / 摩尔投票这道题的。结果也是不孚众望没有打错字啊就是这个孚很绝望啊只是过了一部分的点因为考虑到了这个数据的范围但是没有考虑这个数组空间的大小。回顾一下思路第一遍遍历找候选人第二遍遍历验证候选人是否真的出现超过 n/2 次数组作为参数传入需要知道长度时间O(N),数组也为ON感觉没啥大问题于是我很自然地写出了下面这段代码就提交去了#includebits/stdc.h using namespace std; int vote(int num[], int n) { int cand num[0]; int hp 1; // 第一遍找候选人 for(int i 1; i n; i) { if(hp 0) { cand num[i]; hp 1; } else if(cand num[i]) hp; else hp--; } // 第二遍验证是否确实超过 n/2 if(hp 0) return -1; hp 0; for(int i 0; i n; i) { if(num[i] cand) hp; } return hp n / 2 ? cand : -1; } int main() { int n; cin n; int num[n]; // 变长数组存全部数据 for(int i 0; i n; i) cin num[i]; int flag vote(num, n); cout flag; }结果就是这个很显然易见爆内存了因为除了题目信息意外既然忘记看了这个题目后面的时间限制1.00s 和 内存限制 5.00MB了我使用这个数组产生的空间大小为 2,000,000 × 4B 8,000,000 B是8MB。所以我第二次的优化方向为让这个数组变小一点或者最好不使用数组这样花费的空间变小不就可以通过了吗。第二次提交的思路优化和代码优化更深层的反思我犯了一个根本性的错误摩尔投票法根本不需要存整个数组摩尔投票的核心思想是来一个抵消一个遇到相同的数 → 票数 1遇到不同的数 → 票数 -1同归于尽票数为0 → 换候选人这完全是流式处理只需要记住当前候选人和当前票数两个变量即可。因为在408中出现了这个数组在这个题目当中有这个输入一行整数所以下意识的想到使用数组也就是把它写成了先存再算白白浪费了 O(n) 的空间我们完全可以把这个过程抽象成为打擂台“排好队一个一个来来一个处理一个这样等到遍历完数组整个过程也是结束了。代码如下#includebits/stdc.h using namespace std; int main() { int n,cand0; cinn; int hp0; for(int i0;in;i) { int x; cinx; if(hp0) { candx; hp; } else if(candx) hp; else hp--; } if(hp0) cand-1; coutcand; }另外要说明的是为什么这里不需要第二遍验证重新读一遍题目一共有 n 个正整数ai 他让 redbag 找众数。他还特意表示这个众数出现次数超过了一半。 他的意思是N个正整数里面必然存在如果不存在这个主元素在这个题目当中一定会说明这个主元素不存在要怎么办比如输出-1表示这种很显然就是不存在这个特殊的情况。这种流式处理思维是这次提交得到的最大的收获代码还能这样去优化空间以前考虑的都是在时间层面上的这个思路望我以后一定要记得住。