NC21663. Twilight7和偶像
描述
输入描述
多组数据、随机数据
第一行：数据组数T（1<=T<=50）
每组数据：
第一行： N和M 分别表示点的个数和操作的个数
接下来的M行：每行两个数P和Q分别表示这个操作的起始点和结束点。
输出描述
输出做完所有这些操作后的最小值。
示例1
输入:
1 3 2 1 1 1 3
输出:
7
说明:
对于样例，1号点经过了2次，2号点经过了1次，3号点经过了1次，那么对于排列1 2 3,最小值为1*2+2*1+1*3=7C++11(clang++ 3.9) 解法, 执行用时: 244ms, 内存消耗: 848K, 提交时间: 2020-03-26 14:20:08
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int p[N];
int cmp(int a,int b)
{
return a>b;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m,a,b,i;
long long ans;
memset(p,0,sizeof(p));
cin>>n>>m;
while(m--)
{
cin>>a>>b;
for(i=a;i<=b;i++)
{
p[i]++;
}
}
sort(p+1,p+n+1,cmp);
ans=0;
for(i=1;i<=n;i++)
{
ans=ans+p[i]*i;
}
cout<<ans<<endl;
}
return 0;
}