问题分析：

虽然不能严谨的证明，但是其实自己模拟几组数据再操作一下就发现，无论怎么操作只要每个人的愿望座位定下来，总怒气值就是定值，都不会变（只不过看是谁生气而已 笑）。

其实最简单的或者说最容易想到的方法就是按照题目的说法，用一个数组来记录位置是否被占用，占用就检索下一个是否被占用，最后用下标相减就是怒气值。

但这个算法的时间复杂度可是O(N^2)呀！我们又看到了题目熟悉的0<m<=n<=100000

机智的我又看了一下提交的情况，一半都是TLE超时......说明这个算法不太行。

emmmm也许你和我一样在比赛时一下子失去了方向。

现在比完静下心来思考，其实在证明出无论如何安排总怒气值不变后，难度就降低很多了，你需要考虑的就是如何去计算出结果而已。

我们就按照椅子的顺序来考虑吧，因为每个嘉宾要么直接做到心仪的位置，要么直接往后走，不存在往前走的情况，那么我们就可以设置一个endflag来表示到目前这个椅子为止，坐的最右边的嘉宾的位置。然后后面先判断与endflag的大小关系，再决定是否要计算angry和更新endflag 的方法。

AC代码：

#include <bits/stdc++.h>
using namespace std;

int n[100010];

int main()
{
    int total,guest;
    int t;
    int endflag=0;
    //一定要ll不然会WA
    long long angry=0;
    cin >> total >> guest;
    //用n数组标记每个椅子有多少嘉宾喜欢
    for ( int i=1; i<=guest; ++i )
        cin >> t, n[t]++;
    for ( int i=1; i<=total; ++i)
    {
    //没有嘉宾喜欢的椅子就不用判断
        if ( n[i] )
        {
        //若大于endflag说明这个位置还没有人做 可以占用
            if ( i>endflag )
            {
                if ( n[i]==1 )
                    endflag = i;
                //如果很多人同时喜欢这个位置，那么根据人数更新endflag同时计算angry
                else
                {
                    endflag = i+n[i]-1;
                    t = 1;
                    for ( int j=1; j<=n[i]-1; ++j )
                        angry += t++;
                }
            }
            else
            {
            //若小于，说明这个位置之前的位置肯定已经做满了
            //因为我们是按照椅子的顺序进行遍历的
            //所以这个时候我们就要用另一种方式更新endflag和angry
                endflag += n[i];
                t = endflag;
                for ( int j=1; j<=n[i]; ++j )
                    angry += (t-i),t--;
            }
        }
    }
    if ( endflag > total )
        cout << "-1";
    else
        cout << angry;

}

如果上面更新endflag和angry的计算方法你还是有点不懂，推荐你以

10 8

1 4 4 5 5 6 6 6 

的例子自己在草稿纸上写写就会明白的~

当然，我这个还是太过冗长，可以优化。

比如我可以直接存放每个嘉宾的心仪位置

然后通过endflag=max(m[i],endflag+1)的方式更新，这样就不用讨论那么多种情况了。