排列计算--题解
排列计算
http://www.nowcoder.com/questionTerminal/3c01283b486b40b1be29ea610247d4f5
根据题意可以推出在排列中将出现次数最多的地方放上最大的数，剩下的依次递减。要计算每个位置出现的位置，依据数据范围，暴力模拟会WA，简单差分一下就可以了。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int a[200010];
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
int n, m;
cin >> n >> m;
while (m--)
{
int l, r;
cin >>l >> r;
a[l] += 1;
a[r + 1] -= 1;
}
for (int i = 1;i <= n;i++)
a[i] = a[i - 1] + a[i];
sort(a + 1, a + 1 + n, cmp);
long long int ans = 0,i=1;
while (a[i])
{
ans += a[i] * (n + 1 - i);
i++;
}
cout << ans << endl;
return 0;
}求牛币，QWQ。
