4 条题解

• @ 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;
}

``````
• @ 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;
}

• @ 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;
}

没有想到。。。

• @ 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