4 条题解

  • 0
    @ 2017-11-04 16:53:27

    这道题用到了 "鸽巢原理" ,详细讨论可以先去看一下本题 @gaoj 的题解。然而我在这道题中并没有采用读取 "k" 个数比较重复的策略,而是读取 "(ceil((double)n / k) - 1" 个数比较重复的策略,这个是根据鸽巢原理改写的,这个可以仔细分析下。

    #include<bits/stdc++.h>
    using namespace std;
    int n, k, m;
    int num[15];
    int main () 
    {
        int x, ans=0;
        cin >> n >> k;
        m = n / (ceil((double)n / k) - 1);
        for(int i=1; i<=n && !ans; i+=m)
        {
            x=min(m,n-i+1);
            for(int j=1; j<=x; j++) 
                cin >> num[j];
            sort(num+1, num+x+1);
            for(int j=1; j<x; j++)  
                if (num[j]==num[j+1])
                {
                    ans = num[j];
                    break;      
                }
        }
        cout << ans << endl;
        return 0;   
    } 
    
    
  • 0
    @ 2017-10-14 08:39:52

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int t,x,m;
    int n,k,now;
    int sgin[11];

    bool find(int p)
    {
    for(int i=1;i<=k;i++)
    if(sgin[i]==sgin[p]&&i!=p)
    return true;
    return false;
    }

    int main()
    {
    cin>>n>>k;
    t=1;
    while(t<=n)
    {
    x=t%k;
    if(x==0)
    x=k;

    cin>>m;

    if(m==sgin[x])
    {
    cout<<m;
    break;
    }else
    sgin[x]=m;

    if(find(x)==true)
    {
    cout<<sgin[x];
    break;
    }

    t++;
    }
    return 0;
    }

  • 0
    @ 2015-02-21 00:59:08

    P1939艾酱的七星海棠
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1939 艾酱的七星海棠
    递交时间 2015-02-21 00:58:43
    代码语言 C++
    评测机 Jtwd2
    消耗时间 15 ms
    消耗内存 512 KiB
    评测时间 2015-02-21 00:58:44

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 512 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 508 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 512 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 512 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10

    测试数据 #5: Accepted, time = 15 ms, mem = 512 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 512 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 508 KiB, score = 10

    测试数据 #8: Accepted, time = 0 ms, mem = 508 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 508 KiB, score = 10

    Accepted, time = 15 ms, mem = 512 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    int n , k;
    int i , j;
    int s[9];
    int a;
    bool flag;

    int main()
    {
    scanf( "%d %d" , &n , &k );
    for( i = 0 ; i < n ; )
    {
    for( j = 0 ; j < k && i < n ; j++ , i++ )
    scanf( "%d" , &s[j] );
    sort( s , s + k );
    for( j = 1 ; j < k ; j++ )
    if( s[j - 1] == s[j] )
    {
    flag = 1;
    cout << s[j] << endl;
    }
    if( flag )
    break;
    }
    return 0;
    }

    没有想到。。。

  • 0
    @ 2015-01-27 20:01:25

    [解法1]暴力set,经测试内存消耗为500KiB上下。
    [解法2]分批读取输入数据,一次读取2K个数字,每次在这2K个数字中找重复数字,只要找到了重复的数字就输出。(抽屉原理)之所以每次读取2K而不是K是为了防止一种情况(每组的K个数字中都恰有一个目标数字,最后的零头中也有一个目标数字),但是即使是用K也能解决本题(数据好弱)

    以下测试数据表明了每次应当读入2K个数据而不是K个:
    8 5
    7 1 2 3 4 5 6 7

    • @ 2015-01-28 23:36:34

      不是数据弱,因为这一题说的是cnt[x]*K>N,严格大于N,所以这样的情况可以避免。

    • @ 2015-01-29 21:16:36

      感觉doc神的这个说法貌似还是不能解释我给出的样例。

  • 1

信息

ID
1939
难度
6
分类
其他 点击显示
标签
(无)
递交数
170
已通过
50
通过率
29%
被复制
1
上传者