SGU 127. Telephone directory --- 模拟

127. Telephone directory

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

CIA has decided to create a special telephone directory for its agents. The first 2 pages of the directory contain the name of the directory and instructions for agents, telephone number records begin on the third page. Each record takes exactly one line and consists of 2 parts: the phone number and the location of the phone. The phone number is 4 digits long. Phone numbers cannot start with digits 0 and 8. Each page of the telephone directory can contain not more then K lines. Phone numbers should be sorted in increasing order. For the first phone number with a new first digit, the corresponding record should be on a new page of the phone directory. You are to write a program, that calculates the minimal number P pages in the directory. For this purpose, CIA gives you the list of numbers containing N records, but since the information is confidential, without the phones locations.

Input

The first line contains a natural number K (0 < K < 255) - the maximum number of lines that one page can contain. The second line contains a natural N (0 < N < 8000) - number of phone numbers supplied. Each of following N lines contains a number consisting of 4 digits - phone numbers in any order, and it is known, that numbers in this list cannot repeat.

Output

First line should contain a natural number P - the number of pages in the telephone directory.

Sample Input

Sample Output

【题目大意】

CIA要做一个电话通讯录，通讯录前两页是通讯录的名字和使用说明。
从第三页开始就是正式的通讯录存储。
每条记录占一行，包括电话号码和号码归属地。
每个号码占4位，并且不能用0和8开头。
每页的电话号码条数不能超过K条。
电话号码必须按照升序排序。
如果本页的号码的第一个数字出现新的数字的话，那么就要从下一页开始记录。
写一个程序，计算存储这些号码的最小页数。
但是CIA这个人只给你N个电话号码，并不给你这些电话号码的归属地。（号码不会重复）

K-----一页最多可以存K条
N-----号码总条数

【题目分析】

就是一个统计的问题，直接模拟就行。

//Memory   Time

//  K      MS

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<vector>

#include<queue>

#include<stack>

#include<iomanip>

#include<string>

#include<cmath>

#include<bits/stdc++.h>

using namespace std;

int main()

{

//    freopen("cin.txt","r",stdin);

//    freopen("cout.txt","w",stdout);

    int K,N;

    int cnt[10];

    cin>>K>>N;

    char str[10];

    memset(cnt,0,sizeof(cnt));

    for(int i=0;i<N;i++)

    {

        scanf("%s",str);

        getchar();

        cnt[str[0]-'0']++;

    }

    int page=0;

    for(int i=0;i<10;i++)

    {

        if(cnt[i]%K==0)

        {

            page+=cnt[i]/K;

        }

        else

        {

            page+=cnt[i]/K+1;

        }

    }

    cout<<page+2<<endl;

    return 0;

}

巴特西

SGU 127. Telephone directory --- 模拟

最新文章

热门文章