LightOJ 1148 - Mad Counting (找規律）

Mob was hijacked by the mayor of the Town"TruthTown". Mayor wants Mob to count the total population of thetown. Now the naive approach to this problem will be counting people one byone. But as we all know Mob is a bit lazy, so he is finding some other approachso that the time will be minimized. Suddenly he found a poll result of thattown where N people were asked "How many people in this town otherthan yourself support the same team as you in the FIFA world CUP 2010?"Now Mob wants to know if he can find the minimum possible population of thetown from this statistics. Note that no people were asked the question morethan once.

Input

Input starts with an integer T (≤ 100),denoting the number of test cases.

Each case starts with an integer N (1 ≤ N ≤50). The next line will contain N integers denoting the replies (0to 106) of the people.

Output

For each case, print the case number and the minimumpossible population of the town.

Sample Input	Output for Sample Input
2 4 1 1 2 2 1	Case 1: 5 Case 2: 1

題意：

分别詢問n 個人和他支援同一支隊伍的人數有多少，進而算出城市裡的最少總人數。

思路：

将輸出的人數 y +1，人數有（y+1）的(y + 1） 個集合 可為一組，不足（y+1）個集合的則總人數加 y+1。

使用數組的下标進行循環，0ms AC.

CODE:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int vis[55];
int a[55];
set<int> s;
int main()
{
    //freopen("in.in","r",stdin);
    int T;
    scanf("%d",&T);
    for(int tt=1;tt<=T;tt++)
    {
        int n;
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            a[i]++;
            s.insert(a[i]);
        }
        sort(a,a+n);
        int k=0;
        int ans=0;
        set<int>::iterator it;
        for(it=s.begin();it!=s.end();it++)
        {
            k=upper_bound(a,a+n,*it)-lower_bound(a,a+n,*it);
            ans += (k/(*it))*(*it);
            if(k%(*it) != 0)
            ans += (*it);
        }
         printf("Case %d: %d\n",tt,ans);
    }
    return 0;
}