CodeForces - 1140C

题意：

给你n首歌，每首歌有一个长度ti和一个愉悦度bi，你最多可以从中挑选出来k首歌。那么你挑选出来这首歌会为你增加sum歌愉悦度，sum的求法就是：挑选出来所有歌的长度之和，乘与挑选出来所有歌中愉悦度的最小值。让你输出最大的sum

题解：

看到这道题的第一个想法就是暴力，但是数据显然会让我们TLE，这样的话就把暴力优化一下，我们可以枚举我们挑选出来的这些歌中的最小bi（设这个bi为x），然后这个最小bi这首歌我们必须选上，我们再选择其他歌的时候就要满足其他歌的bi要大于x，且选择歌的数量要小于等于k。

如果之前已经选择了k首歌了，我们就要已选择的歌中从中找出来那个最小的ti，把它扔出去，然后把最小bi这首歌（即，x代表这首歌）放进去

在找最小bi这个过程前，我们可以对这n首歌按照bi从大到小排序，然后用优先队列来维护我们选的歌曲

具体过程见代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<vector>

 7 #include<queue>

 8 #include<map>

 9 using namespace std;

10 typedef long long ll;

11 const int maxn=3e5+5;

12 const int INF=0x3f3f3f3f;

13 const double eps=1e-10;

14 struct shudui

15 {

16     ll bea,len;

17     bool operator < (const shudui x)const

18     {

19         return len>x.len;

20     }

21 }m[maxn],str1;

22 //struct node

23 //{

24 //    ll bea,len;

25 //

26 //};

27 priority_queue<shudui>r;

28 bool mmp(shudui x,shudui y)

29 {

30     return x.bea>y.bea;

31 }

32 int main()

33 {

34     ll n,k;

35     scanf("%lld%lld",&n,&k);

36     for(ll i=0;i<n;++i)

37         scanf("%lld%lld",&m[i].len,&m[i].bea);

38     sort(m,m+n,mmp);

39     ll sum=0,maxx=0;

40     for(ll i=0;i<n;++i)

41     {

42         if (r.size()<k)//没选满k个

43         {

44             r.push(m[i]);//选上

45             sum+=m[i].len;

46             maxx=max(maxx,sum*m[i].bea);//更新答案

47         }

48         else

49         {

50             str1=r.top();

51             sum-=str1.len;

52             r.pop();//踢掉那个最小的

53             r.push(m[i]);//选上新的

54             sum+=m[i].len;

55             maxx=max(maxx,sum*m[i].bea);//更新答案

56         }

57     }

58     printf("%lld\n",maxx);

59     return 0;

60 }

巴特西

CodeForces - 1140C

最新文章

热门文章