2 条题解
-
1
好不容易补完了这道题(我还是太菜了被思维题完虐)
思路就是一个本质贪心,贪心策略为:在满足重量差约束的前提下,让每一头牛尽可能多地占用当前可用的底座。
具体说就是先排序,从最小开始建底,遍历从1-n看每个i能搭上几个塔(包括空塔和之前建过一部分的塔)(判断条件就是和塔顶差大小),存入ans中,然后m是用来存储当前i能用的底,判断的时候加,i的结果出来后减去ans[i],因为目前不确定能不能匹配到,最终答案加上ans[i]。然后具体m为哪些就用双指针去维护,最后输出最终答案
感觉自己说的还是不太好,所以看下代码吧:
#include<bits/stdc++.h> using namespace std; void lhhsyn(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n,m,k,ans[200005]; struct node{ int l,c; }a[200005]; bool cmp(node x,node y){ return x.l<y.l; } long long res=0; int main(){ lhhsyn(); cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>a[i].l>>a[i].c; } sort(a+1,a+n+1,cmp); int l=1;//指针 for(int i=1;i<=n;i++){ while(l<i&&a[i].l-a[l].l>=k){ m+=ans[l++]; } ans[i]=min(m,a[i].c); m-=ans[i]; res+=ans[i]; } cout<<res; return 0; }ps:感觉这个思路你谷的那篇题解写的和**一样,我用了一个多小时才看懂,也可能是我太蒟了(宁老师我们敬仰您口牙)
信息
- ID
- 940
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 108
- 已通过
- 7
- 上传者