2 条题解

  • 1
    @ 2026-10-23 11:52:00

    好不容易补完了这道题(我还是太菜了被思维题完虐)

    思路就是一个本质贪心,贪心策略为:在满足重量差约束的前提下,让每一头牛尽可能多地占用当前可用的底座。

    具体说就是先排序,从最小开始建底,遍历从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:感觉这个思路你谷的那篇题解写的和**一样,我用了一个多小时才看懂,也可能是我太蒟了(宁老师我们敬仰您口牙)

    • @ 2026-10-24 9:10:02

      "(宁老师我们敬仰您口牙)

    • @ 2026-10-27 11:14:52

      @lhhsyn(lhh2012):(宁老师我们敬仰您口牙)

    • @ 2026-10-28 16:55:06

      你们这些坏银看了窝的题解都评论了居然不点赞,窝要谴责你们

  • 1
    @ 2026-10-23 8:17:21

    洛谷P9977 [USACO23DEC] Bovine Acrobatics S

    • 1

    信息

    ID
    940
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    108
    已通过
    7
    上传者