shunfurh
编程介的小学生
2019-02-09 22:41

综合运用算法数据结构解决区间交的问题输出答案,C语言应用的问题

  • Golang
  • r语言
  • erlang

Problem Description
小A有一个含有n个非负整数的数列与m个区间。每个区间可以表示为li,ri。

它想选择其中k个区间, 使得这些区间的交的那些位置所对应的数的和最大。

例如样例中,选择[2,5]与[4,5]两个区间就可以啦。

Input
多组测试数据

第一行三个数n,k,m(1≤n≤100000,1≤k≤m≤100000)。

接下来一行n个数ai,表示lyk的数列(0≤ai≤109)。

接下来m行,每行两个数li,ri,表示每个区间(1≤li≤ri≤n)。

Output
一行表示答案

Sample Input
5 2 3
1 2 3 4 6
4 5
2 5
1 4

Sample Output
10

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

0条回答