第十八章：一文掌握数组标记

数组是一种将数据有序存放的结构，通过一维数组的学习，相信同学们会感觉数组的使用是非常灵活的，原因无异于是因为数组里一个下标对应一个元素。例如 int a[5]={2,3,5,7,11},下标0对应的元素为a[0],下标1对应元素a[1]...,那么在将数组应用在生活或者学习场景中时，下标及其对应的元素就会有不同的含义。

这里有一个有趣的问题：从键盘输入5 个0-9 的数，然后输出0-9 中哪些没有出现过的数。例如，输入2 5 2 1 8 时，输出0 3 4 6 7 9。
大家拿到这道题，第一反应一定是：10个计数器就ok啦！那题目如果输入范围是0-99之间的数，好像得100个计数器了，这个工作量有点繁重呀！
别急，我们就先按照这种思路来捋一下代码：

（1）首先声明10个计数器（可以将计数器看成是标记变量，后续不再累述）：

bool s0=0,s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,s7=0,s8=0,s9=0;

Copy

说明：

s0表示数字0是否出现过,初值为0，表示0还未出现，如果输入的值是0，那么我们需要将s0的改为1；
s1表示数字1是否出现过,初值为0，表示1还未出现，如果输入的值是1，那么我们需要将s1的改为1；
...

s9表示数字9是否出现过,初值为0，表示9还未出现，如果输入的值是9，那么我们需要将s9的改为1；

（2）输入5个数字，并进行10次判断和赋值

for(i=1;i<=5;i++){ 

    cin >> t;

    if(t==0) s0=1;
    
    if(t==1) s1=1;

    if(t==2) s2=1;

    ...

    if(t==9) s9=1;

}

Copy

（3）分别判断这10个标记变量的值，如果某一变量的值为0 ，则说明它的对应数字没有出现过，即这个数没有被标记过，可以输出。如果某一变量的值为1，则说明它的对应数字出现过，即这个数被标记过，不能输出。

if(s0==0) cout<<0<<" ";
if(s1==0) cout<<1<<" ";
if(s2==0) cout<<2<<" ";
...
if(s9==0) cout<<9;
    

Copy

​

细心地同学可能已经发现了，上述代码里，我们声明的那10个标记变量只有两种值，要不为0，要不为1。没有其他值可取。同学们再思考一下就会理解0和1是对应两种状态的，例如若 s1=0,表示1未被标记，这是数字1没有出现的状态，若s1=1,表示1被标记，这是数字1出现的状态。通过s1的值判断1是否出现。

不过你会发现，这样写的代码只适合判断小范围的数。一旦题目的数据范围变大的话，你声明的变量会很多，而且要写的条件判断会很多，代码量是个大问题。

我们写代码要尽量做到短而简洁，其实我们除了这种方法外还可以利用数组+for循环来简化代码：

【分析】：

（1）10个标记变量的用法一样，初始值也全部都是0，所以可以把他们存放在同一个数组a中。 其中a[0] 代表 s0，a[1] 代表 s1...a[9] 代表s9。同时，整个数组初始值为0，所以：int a[10]={0};
初始值全部为0，表示0-9这些数还全都没有出现过呢。

（2）for循环不变，依然需要循环输入5个数字并进行标记。即：

for(i=1;i<=5;i++)
{ 

    cin >> t;

    if(t==0) a[0]=1;

    if(t==1) a[1]=1;

    ....

    if(t==9) a[9]=1;
}

Copy

不难发现，上述for循环部分的if语句满足同一个规律：t的值和进行 =1 操作的变量的下标值是保持一致的，或者说：t就是进行 =1 操作的变量的下标，所以for循环中的10个if语句可以总结为一句：a[t]=1;

（3）对a数组每一个元素进行判断，如果某个a[i]为0，就说明i这个数字没出现过,。如果某个a[i]为1，就说明i这个数字出现过。

说到这里，我们整个代码的构架就已经理清楚了。参考代码如下：

#include
using namespace std;

int main()
{
    bool a[10]={0};//int 型数组也可以实现，不过本题用bool型数组更贴和实际
    int t;
    for(int i=1;i<=5;i++)
    {
        cin>>t;
        a[t]=1;//将编号为t的桶值标记为1，表示t这个数出现过
    }
    for(int i=0;i<=9;i++)
    {
        if(a[i]==0) //或if(!a[i])
        {
            cout< 
Copy
 
理解：
 
cin>>t;a[t]=1;
 
此时此刻你可以将数组的每个小房子看成一个桶，既然小房子有编号，自然而然桶也是有编号的，而且桶的编号也是从0到9.
 
若输入的t为5，那么a[5]=1;
 
元素值
0
0
0
0
0
1
0
0
0
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
下标/桶编号
0
1
2
3
4
5
6
7
8
a[5]的值已经变成1了，说明编号为5的桶被标记了，即数字5出现了。
 记住,判断数字t是否出现过，其实是对数组下标t对应的元素进行判断，即对a[t]进行判断。
 
3.桶标记简单应用 
1.第k小整数 
题目描述：
 
现有n个正整数（n≤10000），要求出这n个正整数中的第k个最小整数（相同大小的整数只计算一次）（k≤100），正整数均不大于300。
 
输入格式：输入共两行。第一行为n和k; 第二行开始为n个正整数的值，整数间用空格隔开。
 
输出格式：第k个最小整数的值；若无解，则输出“NO RESULT”。
 
输入数据#1 
11 4
1 2 3 1 2 3 1 2 3 1 2
 
Copy
 
输出数据#1 
    NO RESULT
 
Copy
 
输入数据#2 
10 3
1 3 3 7 2 5 1 2 4 6
 
Copy
 
输出数据#2 
3
 
Copy
 
【分析】：
 （1）“相同大小的数只计算一次“，这就意味着同样大小的数字，只占一个名次，或者说，在给数字排序的过程中需要有“去重”这一步操作。
 
（2）第k小整数，应当是“去重”之后从小到大数的第k个数字。
 
（3）综上所述，题目要我们输出的就是1,2,3...300这个范围内第k个你所输入的数字，那我们需要准备数组标记1-300范围内哪些数字出现了（不必关心出现的次数），然后准备计数器s，从a[1]到a[300]这个范围内判断当前的a[i]的值，如果a[i]的值非0，就意味着i这个数字出现了，那就s++。
 
  当s==k时，当前的i就是第k小整数。
 
  如果整个a数组遍历完之后的s值小于k，就说明不存在第k小整数。
 
【参考代码】：
 
方法一：
#include
using namespace std;
int a[301];//a数组作为计数器
int main()
{
    int n,k,t,s=0;//s统计当前数字是第几小
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        a[t]=1;
        //这里a[t]=1和a[t]++;的操作都可，因为我们只需要知道哪些数字出现了即可，不关心出现次数 
     } 
     for(int i=1;i<=300;i++)
     {
        if(a[i])//或者if(a[i]==1)
         {
            s++;
            if(s==k)
            {
                cout< 
Copy
 
方法二：
int a[301];//a数组作为计数器
int main()
{
    ...//前半部分代码与方法一一样，只在输出的时候稍微变化一下 
    for(int i=1;i<=300;i++)
    {
        if(a[i])//或者if(a[i]==1)
         {
            s++;
            if(s==k)
            {
                cout< 
Copy
 
2.校门外的树1122 
【题目描述】
 
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
 
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
 
【输入】
 
第一行有两个整数L（1 ≤ L ≤ 10000）和 M（1 ≤ M ≤ 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
 
对于20%的数据，区域之间没有重合的部分；对于其它的数据，区域之间有重合的情况。
 
【输出】
 
包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
 
输入：500 3 150 300 100 200 470 471
 
Copy
 
输出：298
 
Copy
 
 
正在上传…重新上传取消
 
分析：
 
1.这道题首先可以在纸上画出一个数轴，根据题意发现，只有整数点上有树，那么我们可以将这些整数点看成是数组的下标，即整数点0(坐标为0的点)与数组下标0对应，整数1(坐标为1的点)与数组下标1对应...，那么可以声明一个数组a[10001]={0}，数组长度根据L的范围来确定，全部清0，表示从0—1000点上每个点都有一颗树。
 
2.一个坐标点t有两种状态，要不有树，要不没有树，刚才我们已经将数组清0表示每个点都有树了，那么如果坐标点t上的树移走了，是不是可以将a[t]赋值为1，即a[t]=1;表示坐标点t已经被标记，后续判断表示没有树了。
 
3.由于需要移走某些区域的树，那么就说明需要用循环将区间[l,r]间的每个点进行标记。
 
即for(i=l;i<=r;i++)a[i]=1;循环n次即可。
 
例如将一个区间[5,7]的树全部移走;
 
一开始这些点的都有树。
 
元素值
0
0
0
0
0
0
0
0
0
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
下标/桶编号
0
1
2
3
4
5
6
7
8
通过循环进行标记
 即for(i=5;i<=7;i++)a[i]=1;
 
5-7点上的数就被标记成1了。
 
元素值
0
0
0
0
0
1
1
1
0
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
下标/桶编号
0
1
2
3
4
5
6
7
8
循环标记结束后，找元素为0的下标即可。
 
【参考代码】：
 
#include
using namespace std;

int main()
{
    bool a[10001]={0};
    int m,L,l,r,s=0;
    cin>>L>>m;
    for(int i=1;i<=m;i++)//m个区间
    {
        cin>>l>>r;//每个区间的起点与终点
        for(int k=l;k<=r;k++)//确定一个区间
        {
            a[k]=1;//标记,可能会存在对一个点重复标记的情况，但是不影响
        }
    }
    for(int i=0;i<=L;i++)
    {
        if(a[i]==0)//判断未被标记的点的个数
            s++;
    }
    cout< 
Copy
 
3.判断素数2240 
题目描述
 
输入一个自然数，判断这个自然数是不是素数。
 
输入格式
 
输入一个自然数m (2<=m<=32767)
 
输出格式
 
如果m是素数，则输出“Yes”，否则输出“No”。
 
输入：9
 
Copy
 
输出：No
 
Copy
 
这是一道判断素数题，之前我们已经学过用单循环通过对m的因数计数来确定m是否是素数，其实判断素数有很多方法，接下来的方法就是用到了数组标记，即埃拉托色尼筛法，俗称埃氏筛。
 
思考：首先定义一个数组（初始全为 0 ），用来标记每个数字是不是素数（用 0 表示这个数是素数，用 1 表示它不是素数）。初始所有数字是不是素数并不清楚，因此，假设所有数都是素数。但是 0 和 1 肯定不是素数，因此标记为 1，2 肯定是素数，标记为 0。然后可以开始筛选素数了。
 
埃氏筛法的核心思想取决于这样的一个逻辑： 如果后面的数能整除当前的数，那么就表示后面的数有其他因数，那就一定不是素数。把它标记为非素数即可。 素数没有其他因数，因此，不会被标记为非素数。
 
基于以上思想，埃氏筛法在处理时会先去掉 2 的倍数，再去掉 3 的倍数，再去掉 4 的倍数，……依此类推，直到最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数。
 
#include
using namespace std;

const int N = 40005;   // N 的大小取决于问题中 n 的范围
bool a[N];   // 标记数组  a[i] = 0(false):素数，a[i]=1(true): 非素数
// 标记数组也可以用 int 来定义，但占用内存是 bool 的 4 倍
// 因此 bool 能开的数组范围更大，更推荐使用 bool 定义标记数组  

// 埃氏筛法 函数执行完后 a[] 数组即为筛出的素数结果 a[i]=false 表示 i 是素数
int main()
{
    int m;
    a[0]=a[1]=1;         // 0 和 1 不是素数
    cin>>m;
    for(int i = 2; i <= m; i++)
    {
        if(a[i] == 0)   // i 是素数
        {
            for(int j = i+i; j <= m; j += i)
                a[j] = 1;//将i的倍数全部标记为1
        }
    }
    if(a[m]==0)
        cout<<"Yes";
    else
        cout<<"No";
}
 
Copy
 
方法二：
 
#include
using namespace std;
const int N = 32767;   
bool a[N+5];  
void prime()
{ 
    a[0]=a[1]=1;         
    for(int i = 2; i <= N; i++)
    {
        if(a[i] == 0)   
        {
            for(int j = i+i; j <= N; j += i)
                a[j] = 1;
        }
    } 
}
int main()
{
    prime();
    int m;
    cin>>m;
    if(a[m]==0)
        cout<<"Yes";
    else
        cout<<"No";
}
 
Copy
 
4.开灯问题lights1142 
题目描述
 有 n 盏灯，编号为 1∼n。第 11上人把所有灯打开，第 2 个人按下所有编号为 2 的倍数的开关（这些灯将被关掉），第 3 个人按下所有编号为 3 的倍数的开关（其中关掉的灯将打开，开着的灯将被关闭），依此类推。一共有 k个人，问最后有哪些灯开着？
 
输入输出格式
 输入
 两个数 n 和 k(k= 
输出
 开着的灯的编号。
 
样例
 
输入：7 3
 
Copy
 
输出：1 5 6 7
 
Copy
 
思考：
 
分析开关灯的规律
 
① 1号学生会将1、 2、 3、... 푁号灯全部反转。
 
② 2号学生会将2、 4、 6、... 2 * j (2 * j ≤ 푁) 号灯全部反转。
 
③ 3号学生会将3、 6、 9、... 3 * j (3 * j ≤ 푁) 号灯全部反转。
 
④ 푖号学生会将푖、 2푖、 3푖、... 푖 * j (푖 * j ≤ 푁) 号灯全部反转。
 
使用桶排思想，定义数组표푝푒푛， 표푝푒푛[푖]记录푖号灯的状态（开或者关），数组大小
 需要大于灯的最大数量（ > 1000 ）。
 
对于푖号同学，依次反转푖、 2푖、 3푖、... 푥 ∗ 푖(푥 ∗ 푖 ≤ 푁) 号灯。
 
for(int j=1;i*j<=n;j++)open[i*j]=!open[i*j];//改变编号为i*j灯的状态，即关变开，开变关
 
Copy
 
共有푀名学生会进行开关灯操作，从1到푀枚举学生，按照上述方案模拟开关灯。
 
最后，从1到푁枚举所有的灯，如果표푝푒푛 [푖] == 푡푟푢푒，表示푖号灯开着，输出푖
 
方法一：
 
#include
using namespace std;
bool open[1005];//初值为0，默认灯全部为关的状态
int main()
{
    int m,n;
    cin>>n>>m;
    for(int i=1;i<=m;i++)//i模拟人的编号
    {
        for(int j=1;i*j<=n;j++)//i的倍数做为要改变的灯的编号
            open[i*j]=!open[i*j];//开变关，关变开
    }
    for(int i=1;i<=n;i++)
        if(open[i]==1)//为1，说明灯是开的
            cout< 
Copy
 
方法二：
 
#include
using namespace std;
int a[10005];
int main()
{
    int i,j,n,t;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(j%i==0)
            a[j]=1-a[j]; 
        }
    }
    for(i=1;i<=n;i++)
    {
        if(a[i]==1) cout< 
Copy
 
5.整数之和2864 
题目描述
 密码问题迎刃而解，即刻响起一串轻快的开机音乐，哈哈，手机终于可以使用了！忽然，一个神秘的手机精灵从屏幕上出现了，她笑嘻嘻的问卡卡西：“卡卡西，你是不是想见超人啊？”卡卡西迫不及待的点点头，手机精灵说：“那你需要再回答我一个问题。请你随便报出一个正整数nn，我会即刻在手机屏幕上生成一串由递增的不同的正整数所组成的序列，你需要在5分钟内回答出，此序列中有多少个数，恰好等于另外两个数之和。”卡卡西朝着手机精灵自信的一笑，不到一分钟就报出了答案，手机精灵按照之前的承诺，对着手机念了念咒语，“轰”的一声，天空中突然出现一道金光，超人出现啦！卡卡西实在按捺不住心中的喜悦，对着超人大声喊：“超人，超人，我是卡卡西，我要怎样才能拥有你的超能力呢？”，超人轻轻的抚摸着卡卡西的头，笑呵呵的说：“哈哈，卡卡西，你学习努力，又维护正义，你已经是个超人啦……”，说完一个跃起，消失在空中。卡卡西在心中默念：放心吧，超人，我一定会再接再厉，将正义坚持到底……
 
小朋友们，你们知道卡卡西是如何求解的吗？
 
输入格式
 输入数据共两行。数据共两行。 第一行的一个数是指不同正整数的个数n，第二行为空格分割的n个正整数。
 
输出格式
 一个正整数。表示在n个数中恰好等于另外两个数之和的正整数的数目。
 
样例
 
输入：
4
1 3 4 7
 
Copy
 
输出：2
 
Copy
 
输入：
6
1 2 3 4 5 7
 
Copy
 
输出：4
 
Copy
 
数据范围/约定
 样例1解释：因为4=1+3；7=3+4，所以输出为2
 样例2解释：因为3=1+2；4=1+3；5=1+4=2+3；7=2+5=3+4，所以输出为4
 数据范围: 0 
问题简化，首先考虑对于一个整数푥，如何判断푥是否可以由两个整数相加得到？
 双层for循环枚举两个加数，判断是它们的和否等于푥。
 
bool f=0;
for(int i=1;i<=n;i++)
{
    for(int j=i+1;j<=n;j++)//避免出现重复，
    {
        if(a[i]+a[j]==x)
        {
            f=1;//满足条件，标记一次即可退出循环
            break;
        }
    }
    if(f==1)
        break;
}
 
Copy
 
扩展到푁个整数的情况，只需要对a [1] 到a[푁]分别执行上述操作。
 
方法一：
 
#include
using namespace std;
const int N=10005;
int main()
{
    int n,a[N]={0},ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        bool f=0;
        for(int j=1;j<=n;j++)
        {
            for(int k=j+1;k<=n;k++)//避免出现重复
            {
                if(a[j]+a[k]==a[i])
                {
                    f=1;
                    break;
                }
            }
            if(f==1)break;
        }
        if(f==1)ans++;//符合条件的数的个数加1
    }
    cout<
 
Copy
 
这种方法时间复杂度为O(N^3),当n达到1000时，程序基本就会超时了。
 
푁个不同的整数，最多能凑出来多少个不同的加法算式？
 
最多不会超过푁^2个，如果考虑到퐴 + 퐵 == 퐵 + 퐴，最多不会超过푁^2/2个。
 
现在给出方法二：将所有可能的加法算式的和都求出来，然后判断这个和是否在于序列中。
 
for(int i=1;i<=n;i++)
{
    for(int j=i+1;j<=n;j++)//避免重复
        int x=a[i]+a[j];
    if(x∈R)ans++;//伪代码，判断x是否存在序列R中
}
 
Copy
 
如何快速判断所求出来的和是否存在于序列中呢？
 
使用桶排思想，定义数组푠푢푚， 푠푢푚[푖]用来标记整数푖是否存在于序列中，注意：
 
数组大小需要超过序列中最大元素的值。
 
直接判断푠푢푚[푎 [i] + 푎 [j] ]是否为1，如果是1表示푎[i] + 푎[푗]存在于序列푎中。
 
#include
using namespace std;
const int N=1005;
bool sum[2*N];//sum[i]标记i是否存在

int a[10005];
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[a[i]]=1;//对a[i]这个数标记一下
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(sum[a[i]+a[j]]==1)
            {
                ans++;
                sum[a[i]+a[j]]=0;//将s[a[i]+a[j]]设置为0,是因为一个数只能算一次，防止重复计数
                //例如 1+4=5，2+3=5,第一个式子有效，第二个无效
            }
        }
    }
    cout<
 
Copy
 
6.练习题 
约瑟夫问题一 1212
 
猴子选大王monkey 1450
 
狐狸追兔子 1123
 
和为给定数summator 2631
 
二.桶计数 
1.桶计数引入背景 
桶计数是利用数组存储多个计数器，完成大范围内数据出现次数的统计工作的。
 
引入一个同样有趣的问题：现有序号为1—10的小球5个，需要把小球按序号放入对应的盒子里进行分类，要求分类后输出1—10号盒子里的小球个数。
 例如：
 
输入：6 6 1 2 3
 
Copy
 
输出：1 1 1 0 0 2 0 0 0 0
 
Copy
 
根据样例，我们知道数字1,2,3出现的次数为1，6出现2次，其他数没有出现，都为0次。分析发现，这个问题跟我们讲桶标记时的引入的问题很像，那个是让我们输出没有出现过的数，我们用的是桶标记的方法，我们再重温一下写的桶标记代码：
 
#include
using namespace std;

int main()
{
    bool a[10]={0};//int 型数组也可以实现，
    int t;
    for(int i=1;i<=5;i++)
    {
        cin>>t;
        a[t]=1;//将编号为t的桶值标记为1，表示t这个数出现过
    }
    for(int i=0;i<=9;i++)
    {
        if(a[i]==0) //或if(!a[i])
        {
            cout< 
Copy
 
代码中，我们通过数组a[i]的值来判断i是否出现。(a[i]为1表示i出现，为0表示i没有出现)。
 
那么对于当前问题我们能不能用桶来解决呢？答案是肯定的，只不过需要将桶的功能改一下即可，之前是标记为1，现在我们要在标记的基础上改成计数即可，即将上述代码
 
    cin>>t;
    a[t]=1;
 
Copy
 
改成
 
    cin>>t;
    a[t]++;
 
Copy
 
a[t]++的含义是将编号为t的桶里值加1，这里就不仅仅是标记t，还有对t出现的次数进行计数的功能了，通过 ++ 来更新t这个数出现的次数。
 
元素
0
0
0
0
0
0
0
0
0
0
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
a[10]
下标/桶号
1
2
3
4
5
6
7
8
9
10
例如第一次输入t为6，此时需要将6号桶里的值加1。
 
元素
0
0
0
0
0
1
0
0
0
0
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
a[10]
下标/桶号
1
2
3
4
5
6
7
8
9
10
第二次输入t为6，此时需要再将6号桶里的值加1。记住这里不再仅仅是标记为1了，而是继续加1。
 
元素
0
0
0
0
0
2
0
0
0
0
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
a[10]
下标/桶号
1
2
3
4
5
6
7
8
9
10
计数完毕后，直接输出对应桶标号里的值即可，
 
具体代码如下：
 
#include
using namespace std;

int main()
{
    int a[11]={0},t;//必须用int型数组来计数，bool只能用于标记
    for(int i=1;i<=5;i++)
    {
        cin>>t;
        a[t]++;//将编号为t的桶值加1，表示编号为t的球又出现一次
    }
    for(int i=1;i<=10;i++)//一共10个桶，从1到10即可，表示编号
    {
        cout<
 
Copy
 
2.桶计数相关题型： 
输入若干个固定大小范围内的数
 
（1）输出该范围内没有出现过的数字
 
（2）输出该范围内出现过的数字，以及出现的次数
 
（3）统计出现次数最多的数--》众数
 
（4）去重和排序
 
（5）求第k大/第K小数字
 
（6）页码拆分（数位分离+桶计数）
 
3.桶计数应用 
1.桶排序 
问题描述：给定n个整数，将n个整数按照从小到大的顺序输出。(0<= 输入的整数 <=1000)
 
输入：8
     6 3 7 9 2 8 3 10 
 
Copy
 
输出：2 3 3 6 7 8 9 10
 
Copy
 
思考：
 
1.序列中最大元素为1000，准备1001个编号分别为0-1000的空桶。
 
2.依次遍历每个元素，将值为t的元素放入编号为t的桶里。(计数，编号就是用来表示输入的数)
 
3.按照编号从小到大遍历桶，如果桶中的数字不为0，那么将桶的编号i输出。(编号i就是要输出的数)
 
输入前桶值全为0：
 
元素
0
0
0
0
0
0
0
0
0
0
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
...
a[999]
a[1000]
下标/桶号
1
2
3
4
5
6
7
...
999
1000
输入6 3 7 9 2 8 3 10 后的桶值：
 
元素
0
1
2
0
0
1
1
1
1
1
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
a[10]
下标/桶号
1
2
3
4
5
6
7
8
9
10
第3点我们需要着重考虑一下，由于某些数字出现的次数可能不止一次，比如上例中的数字3出现了两次，如果我们在输出时这样写，
 
#include
using namespace std;

int main()
{
    int a[1005]={0},t,n;//准备一个标号为0——1004的桶，有时为了防止溢出，我们的桶可以适当的开大一点
    cin>>n;
    for(int i=1;i<=n;i++)//n个数
    {
        cin>>t;
        a[t]++;//将编号为t的桶值加1，表示编号为t的球又出现一次
    }
    for(int i=0;i<=1000;i++)//标号从0到1000，一一遍历，记住这里不能写 i<=n，这里跟n没关系
    {
        if(a[i]!=0)//数字i出现过
            cout< 
Copy
 
你会发现最终的输出是这样的。自己可以试一试。
 
输出：2 3 6 7 8 9 10
 
Copy
 
跟正确的输出相比少了一个3。这是因为，在输出时，我们用的是条件判断（if(a[i]!=0)），也就是说，对于i号桶，不管里边的值为几，我们都只判断一次，哪怕这个数出现了好几次，我们只输出一次就会对下一个数进行判断，这样就会造成遗漏输出的问题。为了解决这个问题，我们可以用循环去代替这个if判断，直到将i号桶的数输出干净，再对下一个数进行判断。具体代码如下：
 
#include
using namespace std;

int main()
{
    int a[1005]={0},t,n;//准备一个标号为0——1004的桶，有时为了防止溢出，我们的桶可以适当的开大一点
    cin>>n;
    for(int i=1;i<=n;i++)//n个数
    {
        cin>>t;
        a[t]++;//将编号为t的桶值加1，表示编号为t的球又出现一次
    }
    for(int i=0;i<=1000;i++)//标号从0到1000，一一遍历，记住这里不能写 i<=n，这里跟n没关系
    {
        for(int j=1;j<=a[i];j++)//数字i共出现a[i]次，故循环a[i]次即可
        {
            cout< 
Copy
 
2.谁是大赢家 
题目描述：
 
现在有10位选手（编号1--10）来参加歌手大赛，现场n位评委一起为他们投票，谁的票数最多，谁就是最终大赢家，将获得额外的惊喜礼包。现在让我们一起来看看哪位选手夺得了最多的票数。
 
输入格式：输入2行,第1行含1个整数n（1<=n<=100000）,代表评委人数。 第2行包含n个整数，分别表示每个评委的投票编号。
 
输出格式：输出最终赢家的编号。若票数最多的不止一人，则输出最小编号。
 
输入：
10
1 1 2 2 3 3 4 4 5 5
 
Copy
 
输出：1
 
Copy
 
输入：
6
4 3 5 6 5 10
 
Copy
 
输出：5
 
Copy
 
【分析】：
 （1）选手的编号的1-10，所以我们依然需要一个a[11]数组充当计数器的职责。
 
（2）比赛的大赢家即为得票数最多的人，即为a[1]--a[10]中的最大值对应的序号（即下标）。也就是说，这道题需要我们在计数后求最大值，并求出其对应的下标。
 
（3）“若票数最多的不止一人，则输出最小编号。”这句话是说我们要输出a数组中最靠前的最大值的对应下标。
 
这个功能我们在a数组中从前往后找最大值的同时，控制判断条件为if (a[i]>max)即可。如果条件写成if (a[i]>=max)，则会输出最大编号。
 
【参考代码】:
 
#include
using namespace std;
int a[11];//a数组作为计数器，其中a[0]是闲置的 
int main()
{
    int n,t;//n代表数字个数，t代表输入的数字
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        a[t]++;
     } 
     int xb,maxn=0;//xb存储最大值的下标（即对应的数字大小） 
     for(int i=1;i<=10;i++)//注意循环条件，是i<=10 而不是 i<=n 
     {
        if(a[i]>maxn)
         {
            maxn=a[i];
            xb=i;
          } 
     }
    cout< 
Copy
 
【思考】：
 如果题目中允许多位最大赢家活得惊喜礼包，那应该如何更改你的代码？
 
3.页码计数器 
题目描述：
 
一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0，1，2，…，9。其中—个页码不含多余的0，如N＝1234时第5页不是0005，只是5。
 
输入格式：一个正整数N(N≤100)，表示总的页码。
 
输出格式：一行10个正整数，分别是数字0--9出现的次数，用空格隔开。
 
输入：100
 
Copy
 
输出：11 21 20 20 20 20 20 20 20 20
 
Copy
 
输入：11
 
Copy
 
输出：1 4 1 1 1 1 1 1 1 1
 
Copy
 
【分析】：
 （1）题目要统计0-9各自出现的个数，所以需要准备数组：int a[11]=0;
 
（2）书的页码范围是1-n，那我们就要把1--n中所有自然数进行数位分离，这里面n的范围是小于等于100的，则所有的数字只可能是1位数、2位数、3位数这三种情况，所以我们完全可以判断当前的数字是几位数，然后进行相应的数位分离，再在数组对应元素中进行+1的操作。
 
  如果你认为这样麻烦，那也可以采用while循环的方式进行数位分离，思路类似于“回文数判断”。
 
（3）一切计数工作结束以后，直接输出a数组中所有元素就可以啦~ ~
 
【参考代码】：
 
#include
using namespace std;
int a[10];//a数组作为计数器
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t=i;//t是i的“替罪羊”，没有t的话，你的循环可能会变成死循环！
        while(t) //while(t)相当于 while(t>0)
        {
            int ge = t%10; //提取当前的个位
            a[ge]++; //个位是几，这个数值对应的计数器就要+1
            t/=10;//讨论完当前的个位，就可以把它丢掉啦 
        } 
    } 
    for(int i=0;i<=9;i++) //0--9出现的次数，已经存放在a[0]--a[9]这些变量中啦 
    {
        cout<
 
Copy
 
4.第k小整数的变形 
题目描述：
 
现有n个正整数（n≤10000），要求出这n个正整数中的第k个最小整数（相同大小的整数需要计算多次，有几个算几个）（k≤100），正整数均不大于300。
 
输入格式：输入共两行。第一行为n和k; 第二行开始为n个正整数的值，整数间用空格隔开。
 
输出格式：第k个最小整数的值；若无解，则输出“NO RESULT”。
 
输入：
11 11
1 2 3 1 2 3 1 2 3 1 2
 
Copy
 
输出：NO RESULT
 
Copy
 
输入：10 3
1 3 3 7 2 5 1 2 4 6
 
Copy
 
输出：2
 
Copy
 
【分析】：
 （1）“相同大小的数需要计算多次“，这就意味着同样大小的数字，不再是只占一个名次了，要占多个名次了，这个时候就不能是简单的标记为1了，而是需要对出现的数字进行计数了。
 
（2）第k小整数，应当是从第一个出现的数字开始往后数的第k个数。
 
（3）综上所述，题目要我们输出的是按照1—300这个顺序出现的第k个数字，那我们需要准备数组对1-300范围内哪些数字出现了进行计数，然后准备计数器s，从a[1]到a[300]这个范围内判断当前的a[i]的值，如果a[i]的值非0，就意味着i这个数字出现了，那就s++，i出现一次就让s加一次，所以需要循环累加。
 
  当s==k时，当前的i就是第k小整数。
 
  如果整个a数组遍历完之后的s值小于k，就说明不存在第k小整数。其实k>n，就说明不存在第k小的整数
 
【参考代码】：
 
方法一：
#include
using namespace std;
int a[301];//a数组作为计数器
int main()
{
    int n,k,t,s=0;//s统计当前数字是第几小
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        a[t]++;
        //这里a[t]++是为了统计数字t出现的次数 
     } 
     for(int i=1;i<=300;i++)
     {
        while(a[i])//或者while(a[i]>0)
         {
            s++;
            a[i]--;
            if(s==k)
            {
                cout<n) { cout <<"NO RESULT";} 
    return 0;
}
 
Copy
 
方法二：
int a[301];//a数组作为计数器
int main()
{
    ...//前半部分代码与方法一一样，只在输出的时候稍微变化一下 
       //这里s不是每次累加1了，而是每次累加a[i],这样可以将内循环改为条件判断。
    for(int i=1;i<=300;i++)
    {
        if(a[i])//或者if(a[i]>0)
         {
            s+=a[i];//每次加上编号为i号桶里的值。
            if(s>=k)//这里条件需要将s==k改成s>=k,应为一次性加上a[i]可能会超过k,但是第k小的数还是i
            {
                cout<n) { cout <<"NO RESULT";} 
    return 0;
}
 
Copy
 
5.集福小游戏 
题目描述：
 
奥斯卡想要很多魔法帽，但是兑换一顶魔法帽需要编号1—10的福卡各一张，现在奥斯卡手上有若干张福卡，他想要知道，他能够兑换多少顶魔法帽，现在需要你你能帮他编写一个程序帮他解决这个问题。
 
输入格式：
 输入共两行，第一行为n，表示共有n张福卡，第二行为n个1—10的数，表示每张福卡上的编号。(10<=n<=1000)
 
输出格式
 输出共一行，表示奥斯卡能够兑换的魔法帽的总数
 
输入：
15
5 2 3 6 4 8 9 7 2 6 2 1 7 2 5
 
Copy
 
输出：0
 
Copy
 
输入：
15
5 2 3 6 4 8 9 7 2 6 2 1 10 2 5
 
Copy
 
输出：1
 
Copy
 
样例1
 
元素
1
4
1
1
2
2
2
1
1
0
下标/桶号
1
2
3
4
5
6
7
8
9
10
样例2
 
元素
2
4
1
1
2
2
1
1
1
1
下标/桶号
1
2
3
4
5
6
7
8
9
10
样例1说明: 15张福卡中没有 编号为10的福卡，所以兑换不了魔法帽。10号福卡最少，为0。
 样例2说明： 15张福卡可以兑换一顶魔法帽。福卡最少数量为1。
 
观察发现，可兑换的魔法帽的数量与数量最少的福卡一致，那么我们可以利用桶计数的思想找最小值即可。
 
思路：
 
 
定义数组a[15]，使用a[t]记录编号为t的福卡的总数量。
  
每读取一张福卡푡，就更新编号为푡的福卡数量：a [t] + +;
  
循环查找a[1] 到a[10]的最小值，就是问题的答案。
 
【具体代码】
 
#include
using namespace std;
int a[15];//a数组作为计数器
int main()
{
    int n,t,minx=101;//minx表示能够兑换的魔法帽的数量，由于n最大为1000，每个福卡
    //等概率出现，最多可以兑换1000/10=100张。所以minx初值为101即可，minx=INT_MAX也可以
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        a[t]++;
        //这里a[t]++是为了统计数字t出现的次数
     } 
     for(int i=1;i<=10;i++)
     {
         if(a[i] 
Copy
 
6.成绩统计2667 
题目描述
 
  期末考试结束了，学校已批改完所有试卷，已知某年级共有 n 位学生和他们对应的成绩。老师们想知道这个年级学生成绩的分布情况，以便下学期更好的开展教学，因此现在需要统计一些数据如下：
 
  1）全校最低分、最高分的成绩及人数；
 
  2）同分最多的成绩和人数，如果人数相同，依次由低分到高分输出；
 
  3）分值 p 和 q 之间（包含 p 和 q）人数。
 
  请同学们编程帮忙统计吧。
 
输入格式
   输入数据共 3 行。第一行一个整数 n，表示学校某年级总人数，第二行共有 n 个由空格分隔的正整数，表示每一位学生成绩。第三行共有 2 个由空格分隔的正整数 p 和 q。
 
输出格式
   共 4 行，第一行 2 个由空格分隔的正整数，对应最低的成绩及人数，第二行 2 个由空格分隔的正整数，对应最高的成绩及人数，第三行多个由空格分隔的正整数，对应多个相同分数最多的成绩及人数。第 4 行 1 个正整数，对应成绩 p 和 q 之间人数。
 
输入：
11
80 85 80 78 90 95 95 80 98 78 95
85 95
 
Copy
 
输出：
78 2
98 1
80 3 95 3
5
 
Copy
 
数据范围/约定
   对于 100% 的测试数据满足：1≤学生人数 n≤10000，0≤每个学生成绩≤500.
 
思考：
 
1.本题可以使用桶计数的方法解决，由“0≤每个学生成绩≤500 ”可知，准备一个计数数组，编号0—500即可，int a[505];将每个学生的成绩记录到对应的桶里。
 
2.声明分数最大值及最小值 max1,min1,同分最多的人数max2,循环更新即可，对于“同分最多的成绩和人数，如果人数相同，依次由低分到高分输出”这一要求，我们可以从小到大判断。
 
3.最后再用一个循环查找分数在p—q间的人数即可，输出对应桶值即可。
 
具体代码：
 
#include
using namespace std;
int a[501]={0};
int main()
{
    int n,i,max=-1,min=999,max2=-1,ans=0;
    int p,q,t;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>t;
        a[t]++;//考取分数t的人数加1
        if(tmax)//找分数最大值 
            max=t;
        if(max2>p>>q;
    cout< 
Copy
 
7.成绩排名2649 
题目描述：
 
某次信息学测试一共有4道题目，每题有10个测试点，每个测试点10分，学生得分肯定都是整数，最多400分，最少0分。现给出本次测试n个同学的成绩，请统计输出每个同学前面有多少人分数比他高。
 
输入格式
 共2行。
 第一行一个正整数n；
 第二行n个用空格隔开的整数，表示每个同学的成绩。
 
输出格式
 输出共一行，n个整数，第i个表示第i位同学前面比他分数高的人数。
 
样例
 输入#1
 10
 220 100 400 360 180 250 300 400 200 190
 
输出#1
 0 1 0 1 3 2 2 0 6 7
 
解释#1
 第1个同学220分，他前面有0人比他分数高；第2个同学100分，他前面有1人比他分数高，即考了220的人；第3个同学400分，他前面有0人比他分数高；……；第10个同学190分，他前面有7人比他分数高，即考了220分、400分、360分、250分、300分、400分和200分的7个人。
 
数据范围/约定
 30%的数据1<=n<=10000
 100%的数据1<=n<=100000
 
方法一：
 题意：猛地一看数据范围特别大，for循环估计要超时了，在仔细一看数据：就400分，那么大量数据中必定重复（这题数字都是整数， 所以也就40个数字而已），标记一下就可以了。找到相同的数字就不用再往后找了
 
具体代码：
 
方法一
#include
#include
using namespace std;
int bg[100005],sc[100005];//bg[i]表示前i-1个同学里比第i个同学分数高的人数
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sc[i];//第i个同学的成绩
        for(int s=i-1;s>=1;s--){//判断第i个同学前边比他高的人数
            if(sc[s]>sc[i])
                bg[i]++;//在前i-1个同学里，比i同学分数高的人数加1
            else if(sc[s]==sc[i]) {//减少循环，第s位同学分数与第i位同学分数相同。bg[i]可以由累加bg[s]得到
                bg[i]+=bg[s];
                break;  
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout< 
Copy
 
法2：如果出现一个200那么就有比0-199都大的数字了，把f[0]-f[199]都标记加1 备注：本题数据特殊 只有整十数 所有可以标记整十的数字就可以了。
 
#include
using namespace std;
int a[410];//将分数作为桶的标号
int main()
{
    int n,t,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t;//第i位同学考的分数为t
        a[t]++;//考取分数t的人数加1
        for(int j=t+1;j<=400;j++){//判断前i-1位同学里有多少人考的分数比t高
            if(a[j]){
                cnt+=a[j];
            }
        }
        cout< 
Copy
 
8.直播获奖2659 
题目描述
 
  NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%，即当前排名前 w% 的选手的最低成绩就是即时的分数线。
 
  更具体地，若当前已评出了 p 个选手的成绩，则当前计划获奖人数为 max(1,⌊p×w%⌋)，其中 w 是获奖百分比，⌊x⌋ 表示对 x 向下取整，max(x,y) 表示 x 和 y 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
 
  作为评测组的技术人员，请你帮 CCF 写一个直播程序。
 
输入格式
   输入文件名为 live.in。
 
  第 1 行两个正整数 푛, 푤。分别代表选手总数与获奖率。
 
  第 2 行有 n 个非负整数，依次代表逐一评出的选手成绩。
 
输出格式
   输出文件名为 live.out。
 
  只有一行，包含 n 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。
 
样例
 输入#1
 10 60
 200 300 400 500 600 600 0 300 200 100
 
输出#1
 200 300 400 400 400 500 400 400 300 300
 

 
 
输入#2
 10 30
 100 100 600 100 100 100 100 100 100 100
 
输出#2
 100 100 600 600 600 600 100 100 100 100
 
样例3 见选手目录下的 live/live3.in 与 live/live3.ans。
 
数据范围/约定
 
测试点标号
n
1~3
=10
4~6
=500
7~10
=2000
11~17
=10000
18~20
=100000
  对于所有测试点，每个选手的成绩均为不超过 600 的非负整数，获奖百分比 푤 是一个正整数且1≤w≤99。
 
  在计算计划获奖人数时，如用浮点类型的变量（如 C/C++中的 float、double，Pascal 中的 real、double、extended 等）存储获奖比例 w%，则计算 5×60% 时的结果可能为 3.000001，也可能为 2.999999，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。
 
这道题数据比较大，使用sort()排序肯定会超时。
 
#include 
using namespace std;

int a[1000000], n, w, k;
int main()
{
    cin >> n >> w;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sort(a+1, a+i+1, greater());
        k = max(1, int(i*w/100.0));
        cout << a[k] << ' ';
    }
    return 0;
}
 
Copy
 
由于分数最高为600，因此可以声明一个数组用来计算每个分数的学生人数，时间复杂度为O(600×n),不会超时。
 
#include 
using namespace std;

const int N = 1e5+5;
int n, w, t, cnt[601], sum, line;

int main()
{
    freopen("live.in", "r", stdin);
    freopen("live.out", "w", stdout);
    cin >> n >> w;
    for(int i = 1; i <= n; i++)
    {
        cin >> t;
        cnt[t]++;//考取分数t的人数加1
        sum = 0;
        line = max(100, i*w/100*100);  // 分数线，分数线随着i的变化而变化
        for(int j = 600; j >= 0; j--)//从大到小排
        {
            sum += cnt[j];             // 达当前线人数
            if(sum*100 >= line)
            {
                cout << j << " ";
                break;
            }
        }
    }
    return 0;
}
 
Copy
 
4.练习题 
入门:
 
一个萝卜一个坑 1654
 
小球 1655
 
求n个数中每个数出现的次数 1884
 
声音识别 1725
 
缺失的数字 2029
 
找筷子 1472
 
去除重复数字 1183
 
基础:
 
求n个数中出现次数最多的数 1883
 
数字出现次数 1180
 
选班委 2005
 
众数 1657
 
明明的随机数 1159
 
宇宙总统 3432
 
换届选举 1658
 
第k小整数 1673
 
提高:
 
猴子吃香蕉 1689
 
神奇药水 1396
 
绘制垂直柱状图 1871
 
扑克牌组合 1334
 
夏令营小旗手 1557
 
求N个整数的平均数、众数和中位数 1179
 
COUNT 1178
 
梦中的统计 1554