人生第一篇题解,虽然这道题做的人暂时不多,但我相信它——迟早有一天会发扬光大的!!!说完废话
步入正题
题意:
传送门
思路:
模拟、枚举
对于每个组里的数字,先排序,然后从一到最大可能的情况,枚举要选几个数
记录选取的和(用前缀和会更方便),然后就是选择
那些前缀和
为 正数的组 加进来
为 负数的组 舍去(因为出现负数的情况说明这组还未选进来的数都是负数,没有利用价值了,故舍去)
具体实现起来比较麻烦
把每个数分到相应的组,并把每个组里的数排序 ——》 先对全部的数排序,再用链式前向星分组
枚举 数的个数: → 用queue记录遍历的顺序,再用两个while循环遍历,res表示有价值的组的个数,里面的num表示这一次遍历了几个组(方便终止)
具体见代码
#include<bits/stdc++.h> using namespace std; struct node{ int s,r; }a[100010]; int nxt[100010]; int head[100010]; int s[100010]; int sum,cur,ans,num,res; int n,m; int read()//快读不解释 { int s=0,p=1; char c=getchar(); while(!isdigit(c)) { if(c=='-') p=-1; c=getchar(); } while(isdigit(c)) { s=(s<<1)+(s<<3)+c-'0'; c=getchar(); } return s*p; } bool cmp(node x,node y) { return x.r<y.r; } int main() { int i; n=read();m=read(); for(i=1;i<=n;i++) a[i].s=read(),a[i].r=read(); sort(a+1,a+1+n,cmp);//先进行排序 for(i=1;i<=n;i++)//分组 { nxt[i]=head[a[i].s]; head[a[i].s]=i; } queue<int>p; for(i=1;i<=m;i++)//起始遍历顺序就是组号 p.push(i); res=m; while(res)//有价值的组数 { num=res;//更新下次 sum=0;//记录这次的结果 while(num--) { cur=p.front();p.pop(); s[cur]+=a[head[cur]].r;//前缀和 sum+=max(s[cur],0); head[cur]=nxt[head[cur]];//更新头结点 if(head[cur]&&s[cur]>0)//如果还有利用价值就加入下一次的遍历序列 p.push(cur); else//否则更新组数 res--; } ans=max(ans,sum);//全部的答案 } printf("%d",ans); return 0; }