Think: 1知识点：map/桶记录/基础dp 2题意：输入n个数，输出出现次数大于等于(n+1)/2的那个数
vjudge题目链接
以下为Accepted代码——map-421ms
#include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; int main(){ int n, k, i, x, ans; while(~scanf("%d", &n)){ k = (n+1)/2; map <int, int> m; m.clear(); for(i = 1; i <= n; i++){ scanf("%d", &x); m[x]++; if(m[x] >= k) ans = x; } printf("%d\n", ans); } return 0; }以下为Accepted代码——桶记录-265ms
#include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; int book[1001400]; int main(){ int n, k, i, x, ans; while(~scanf("%d", &n)){ k = (n+1)/2; memset(book, 0, sizeof(book)); for(i = 1; i <= n; i++){ scanf("%d", &x); book[x]++; if(book[x] >= k) ans = x; } printf("%d\n", ans); } return 0; }以下为Accepted代码——基础dp-156ms
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main(){ int n, i, x, ans, sum; while(~scanf("%d", &n)){ sum = 0; for(i = 1; i <= n; i++){ scanf("%d", &x); if(!sum){ ans = x; sum++; } else { if(x != ans) sum--; else sum++; } } printf("%d\n", ans); } return 0; }