排列计算 题解（java）
排列计算
https://ac.nowcoder.com/acm/contest/5477/F
考点：贪心+差分
首先我们要考虑计算每个位置的访问次数。
我们可以用差分来计算每一个位置访问了多少次。
然后排序，将从小到大以此乘以1 2 3 4~~~，求和即可。
import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
public static void main(String args[])throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n = (int)in.nval;
in.nextToken();
int m = (int)in.nval;
long num[] = new long[n];
long p[] = new long[n+1];
for(int t=0;t<m;t++)
{
in.nextToken();
int l = (int)in.nval;
in.nextToken();
int r = (int)in.nval;
p[l-1]+=1;
p[r]-=1;
}
num[0] = p[0];
long u=p[0];
for(int i=1;i<n;i++)
{
num[i] = p[i]+u;
u+=p[i];
}
long sum=0;
Arrays.sort(num);
for(int i=0;i<n;i++)
{
sum+=(num[i]*(i+1));
}
out.print(sum);
out.flush();
}
} 
