Codeforces Round龚304(Div.2)B.Soldier and Badges水題

B.Soldier and Badges
Time Limit：20 Sec  メモリLimit:256 MB
タイトル接続
http://codeforces.com/contest/546/problem/B
Description
Colonel has n badge s.He wants to give one badge to everry of his n solders.Each badge has a coolness factor，which shows howmucit's owner reached.Coolnes factor can be incread byone for cone.coone.coone.coone
For everry pair of sourdiers one of them shound get a badge with stritly higher factor than the second one.Exact values of their factors ares't import，they just need to have distinctors.
Colonel knows，which sodier is supposed to get which badge initially，but there is a problem.Some of badges may have the same factor of coolness.Help hi and calculate howmucmoney hars hars hast baide formadentings。
Input
First line of input consists of one integer n（1̵≦𔎅n̵≦𔎅3000）
Next LINE consists of n integers ai（1̵≦̵ai̵≦̴n）、which stand for coolnes factor of each badge.
 
Output
Output single integer-minimum amount of coins the colonel has to pay.
 
Sample Input
4
1 3 1 4
Sample Output
1
HINT
 
題意
1元で勲章を一つ追加してください。いくらかかりますか？勲章は全部違っています。
クイズ:
暴力ですか
コード:
 

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200001
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
/*

inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
*/
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
//**************************************************************************************

int a[maxn];
int b[maxn];
int main()
{
    int n=read();
    for(int i=0;i<n;i++)
    {   
        a[i]=read();
        b[a[i]]++;
    }
    sort(a,a+n);
    int ans=0;
    for(int i=0;i<maxn;i++)
    {
        if(b[i]>1)
        {
            ans+=b[i]-1;
            b[i+1]+=b[i]-1;
            b[i]=1;
        }
    }
    cout<<ans<<endl;
}