H Kuangyeye and hamburgers

链接：https://ac.nowcoder.com/acm/contest/338/H
来源：牛客网

题目描述

Kuangyeye is a dalao of the ACM school team of Hunan University. His favorite food are hamburgers. One day, Kuangyeye came to the KFC(or maybe McDonald) and saw n hamburgers on the counter.The weight of the i-th hamburger was w _i. Since he likes hamburgers very much, he would like to buy some hamburgers. Considering his weight or other factors, Kuangyeye only wanted to eat all the hamburgers from the a-th heaviest to the b-th. Since Kuangyeye is fickle, he had k plans before buying hamburgers. The i-th plan gives a _i and b _i. Please help Kuangyeye calculate the maximum weight of hamburgers he can eat among the k plans.

输入描述:

the first line of input contains two integer n and k--the number of hamburgers on the counter and the number of plans Kuangyeye had;
the next line contains n integer--the i-th integer represents the weight of i-th hamburger,namely w

_i

;
Each the following k line contains two integer a

_i

 and b

_i

 ,represents Kuangyeye's strategy in his i-th plan.

输出描述:

Output contain a single integer,represents maximum weight of hamburgers Kuangyeye can eat.

示例1

输入

复制

5 2
4 3 5 2 6
1 1
3 4

输出

复制

7

说明

Kuangyeye's first plan was to eat the hamburger weighing 6；

and his second plan was to eat the hamburger weighing 3 and 4;

So the maximum weight of hamburgers he can eat was 7.

备注:

1≤n,k≤100000,1≤a

_i

≤b

_i

≤n,1≤w

_i

≤10000

题解：排序，计算前缀和，模拟

#include 
#include 
using namespace std;
int w[100050];
long long dp[100050];bool cmp(const int& a,const int& b) {return a>b;
}int main() {int n,k;long long ans=0;cin>>n>>k;for(int i=1;i<=n;i++) cin>>w[i];sort(w+1,w+n+1,cmp);dp[0]=0;for(int i=1;i<=n;i++) {dp[i]=dp[i-1]+w[i];}while(k--) {int l,r;cin>>l>>r;ans=max(dp[r]-dp[l-1],ans);}cout<endl;return 0;
}

 

转载于:https://www.cnblogs.com/DWVictor/p/10229893.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！