今天中午1小時(shí)，定時(shí)兩道，我就知道自己的太陽(yáng)降落了。。。orz

文章目錄

• 題目
• 題解
• 代碼實(shí)現(xiàn)

題目

PB 帶來(lái)了若干只蒟蒻。
眾所周知，NTF 是數(shù)論學(xué)會(huì)的會(huì)長(zhǎng)，于是 PB 準(zhǔn)備用數(shù)字擊敗 NTF，以證明 PB 比 NTF 更強(qiáng)。
于是 PB 準(zhǔn)備了一些卡片，并在每個(gè)蒟蒻頭上都貼了一張卡牌。每個(gè)卡牌上都寫(xiě)了一個(gè)數(shù)字。
由于蒟蒻太弱了，甚至不會(huì)看鏡子來(lái)了解自己頭上的數(shù)字，但他們由于經(jīng)常被大佬吊打，所以觀察力敏銳，他們都知道別人頭上的數(shù)字。

第 i 個(gè)蒟蒻會(huì)告訴你他看到了 ai 種數(shù)字(定義兩個(gè)數(shù)字不同種當(dāng)且僅當(dāng)它們的值不同)

但是由于蒟蒻太弱了，可能會(huì)報(bào)錯(cuò)數(shù)據(jù)，NTF 需要核實(shí)是否有一種情況使所有蒟 蒻說(shuō)的話都正確。(可能情況不唯一)

輸入格式
多組測(cè)試，文件第一行一個(gè)整數(shù) T，表示測(cè)試數(shù)據(jù)組數(shù);
對(duì)于每組數(shù)據(jù)，第一行，一個(gè)整數(shù) n，表示蒟蒻的數(shù)量;
第二行，n 個(gè)整數(shù)用空格隔開(kāi)，表示數(shù)組 ai，意義同題面。
輸出格式
如果至少有一種情況使所有蒟蒻的話都正確，輸出"yes"，否則，輸出"no"。

樣例
樣例輸入
2
2
1 1
4
1 3 2 2
樣例輸出
yes
no
數(shù)據(jù)范圍與提示
對(duì)于所有數(shù)據(jù)，T<=10
對(duì)于 20% 的數(shù)據(jù)，N≤8
對(duì)于所有數(shù)據(jù)，1≦N≤1000000, 0≦ai<N

題解

首先，我們應(yīng)該明確的最好找的規(guī)律就是：

看到的種類(lèi)的最大值Max和最小值Min的差不應(yīng)該超過(guò)1

證明：假設(shè)i看到了x種，j最大的情況也就是i是唯一的數(shù)字，而有k的數(shù)字與j相同，
這樣也最多是看見(jiàn)了x+1種。

這樣我們接下來(lái)就只用分類(lèi)討論Max = Min和Max = Min + 1的情況

1.Max = Min：
（1)顯而易見(jiàn)，當(dāng)Max + 1 = n時(shí)，是成立的，每一個(gè)i都是獨(dú)一無(wú)二的數(shù)字
（2)當(dāng)Max * 2 <= n時(shí)也是成立的，因?yàn)橐S持i看到的種類(lèi)不變，就必須至少要有一個(gè)a[j]=a[i]
所有要保證每個(gè)數(shù)至少出現(xiàn)兩次

2.Max = Min + 1：有點(diǎn)雜，請(qǐng)仔細(xì)品味！！
我們先假設(shè)i報(bào)出的數(shù)有a[j]=a[i]的情況，那么就意味著i報(bào)出的數(shù)一定是Max

證明：設(shè)i報(bào)出了a[i]，如果有a[j]=a[i]，它就相當(dāng)于照了一面鏡子，看得見(jiàn)自己的數(shù)，
它報(bào)出的種類(lèi)中有一種是自己，即Max，而如果i是獨(dú)一無(wú)二的數(shù)字，它報(bào)出的種類(lèi)就會(huì)少一種，即Min

所以，報(bào)出的數(shù)是Min的數(shù)的i頭頂上的數(shù)是獨(dú)一無(wú)二的

所以當(dāng)我們確定了報(bào)出Min的i的個(gè)數(shù)有tot個(gè)的時(shí)候，剩下的n-tot個(gè)人報(bào)的就都是Max了
而對(duì)于這Max的考慮就可以變?yōu)榍闆r1的做法

這里送幾組數(shù)據(jù)給大家:

na[i]yes/no

5	2 2 3 3 3	yes
5	2 2 2 3 3	no
5	2 2 2 2 3	no
3	1 2 2	yes
7	3 4 4 4 4 4 4	yes
6	3 4 4 4 4 4	no
4	2 2 2 1	yes

代碼實(shí)現(xiàn)

如果有的犇犇被數(shù)據(jù)卡了，可以加個(gè)讀入優(yōu)化，還可以把第二個(gè)tot循環(huán)并到第一個(gè)里面
但是本xxjAC了，我就不改了。。

#include <cstdio> #include <iostream> using namespace std; #define MAXN 1000005 int t, n, Min, Max; int a[MAXN]; int main() {scanf ( "%d", &t );while ( t -- ) {scanf ( "%d", &n );Min = 0x7f7f7f7f;Max = 0;for ( int i = 1;i <= n;i ++ ) {scanf ( "%d", &a[i] );Min = min ( Min, a[i] );Max = max ( Max, a[i] );}if ( Max - Min > 1 ) printf ( "no\n" );else {if ( Max == Min && ( Max == 1 || Max == n - 1 ) ) printf ( "yes\n" );else {if ( Max == Min ) {if ( ( Max << 1 ) <= n || Max + 1 == n ) printf ( "yes\n" );else printf ( "no\n" );}else {int tot = 0;for ( int i = 1;i <= n;i ++ )if ( a[i] == Min ) tot ++;if ( ( ( Max - tot ) << 1 ) <= ( n - tot ) && tot < Max ) printf ( "yes\n" );else printf ( "no\n" );}}}}return 0; }

把這道題甩在這兒啦，這里是勵(lì)志要做進(jìn)中國(guó)前100強(qiáng)的公司，有問(wèn)題請(qǐng)call：139紅酒白酒葡萄酒
有不理解的或者補(bǔ)充的歡迎大犇在評(píng)論區(qū)留言。。。

總結(jié)

以上是生活随笔為你收集整理的数数字的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。