【map/桶记录/基础dp】Ignatius and the Princess IV HDU - 1029

快来打我* 2022-06-10 01:16 210阅读 0赞

Think:  
1知识点：map/桶记录/基础dp  
2题意：输入n个数，输出出现次数大于等于(n+1)/2的那个数

[vjudge题目链接][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;
    }

[vjudge]: https://vjudge.net/contest/163018#problem/B