投稿 资料上传 搜索
您现在的位置是: 首页 > 文章 > 正文

“科大讯飞杯”高校网络友谊赛F:排列计算

链接:https://ac.nowcoder.com/acm/contest/5477/F
来源:牛客网

题目描述

天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International Competition of Permutation Calculation, ICPC) 的比赛,这个比赛的规则是这样的: 

一个选手给出一个长度为 n 的排列,另一个选手给出 m 个询问,每次询问是一个形如 (l, r) 的数对,查询队友给出的排列中第 l 个数到第 r 个数的和,并将查询到的这个区间和加入总分,最后总分最高的队伍就能获胜。

石头手速很快,在比赛一开始就给出了 m 个询问;菜哭武也很强,他总是能找到最合适的排列,使得他们队的总分尽可能高。

在看比赛直播的你看到了石头给出的 m 个询问,聪明的你能不能预测出他们队伍最终的得分呢?

一个排列是一个长度为 n 的数列,其中 1 ~ n 中的每个数都在数列中恰好出现一次。比如 [1, 3, 2] 是一个排列,而 [2, 1, 4] 和 [1, 2, 3, 3] 不是排列。 

输入描述:

第一行输入两个数 n (1≤n≤2×105) 和 m (1≤m≤2×105) 。
接下来 m 行,每行输入两个数 l 和 r ,代表这次查询排列中第 l 个到第 r 个的和。

输出描述:

输出一个整数,代表他们队伍总分的最大值。
示例1

输入

复制
7 3
1 3
3 7
5 6

输出

复制
46

说明

一个符合条件的排列是 [1,3, 6, 4, 7, 5, 2],于是最终的得分为 (1 + 3 + 6) + (6 + 4 + 7 + 5 + 2) + (7 + 5) = 46


解题思路:

要把最大的数放在最多出现的位置上,把第二大的数放在第二多出现的位置上,依次类推,才可以获得总分的最大值。

差分计算每个位置出现的最高次数,然后乘上相应的数。

AC代码:

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 2*1e5+10;
int a[N];
int cmp(int a, int b)
{
return a>b;
}
int main()
{
int n, m, l, r;
scanf("%d%d", &n, &m);
while(m--)
{
scanf("%d%d", &l, &r);
a[l]++;
a[r+1]--;
}
for(int i=1; i<=n; i++)
a[i] += a[i-1];
sort(a+1, a+n+1, cmp);

long long ans = 0,x=n;

for(long long i=1; i<=n ; i++)
ans+=(n-i+1)*a[i];

printf("%lld\n", ans);
}



转载于:

文章标签:
阿里云服务器采购季
给作者打赏,鼓励TA抓紧创作!
评论