首页 > 代码库 > soj 4389模拟
soj 4389模拟
背景:周赛A题,
学习:1.开始没有注意到题目中对于帖子数大于1/2的描述,纯暴力计数,各种超!
2.后来发现按顺序扫描每一个数看是否有它在数组中的数量大于1/2,是则找到。我的代码:
#include<stdio.h> #include<string.h> int str[10000000]; int main(void) { int n; scanf("%d",&n); while(n--) { int m,cout=0; scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%d",&str[i]); } for(int i=0;i<m;i++) { for(int j=0;j<m;j++) { if(str[j]!=-1){ if(str[j]==str[i]) { cout++; if(cout>=m/2+1) { printf("%d\n",str[i]); goto l1; } } } } str[i]=-1; cout=0; } l1: cout=0; } return 0; }
3.这样能过但是开了巨大的内存(oj极限是10的8次方个int?)
解题报告给出了比较先进的方法:假定第一个数是并计数count为1,以后遇见和它相同的就count自增一,当count为0时,可以就变为当前读入的数,最后剩下的可以必然是要找的大于1/2的数。给出代码:
#include<stdio.h> #include<string.h> int str[10000000]; int main(void) { int n; scanf("%d",&n); while(n--){ int m,count=0,x,key=-1; scanf("%d",&m); while(m--){ scanf("%d",&x); if(x!=key) count--; else count++; if(count<0) { key=x; count=0; } } printf("%d\n",key); } return 0; }
soj 4389模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。