本文主要是介绍USACO 2023 December, SilverProblem 1. Bovine Acrobatics题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有n件物品，m组叠罗汉，相邻罗汉差值至少为k。
第i件物品的重量和数量
由于m最大范围为1e9，开辟m组罗汉槽存储罗汉值，内存空间不够。
分析样例：
3 5 2 9 4 7 6
5 5
一开始我想的是层数，但是一层中存在数据不同的情况，没有办法区别，比如第一行有9和7，在第二行放置7时候如何解决7不放在7上，开辟数据记录，存储空间不够
不考虑槽的层数，只考虑放置情况，发现需要每次统计放置到最外面的情况。
初始化罗汉为1e9，第一次必定可以被覆盖。
ans第一次可以统计4个9，因为4个9全部可放置于1e9上
ans第二次可以统计1个7，因为1e9剩下1个槽可以放置
ans第三次可以统计4个7，因为9-7<=2,7放在9的上面
ans第四次可以统计1个5，剩下一个槽位放置5
ans第五次可以统计4个5，全部可放置。
那么可以覆盖当前罗汉就可以进行统计。
设置两个指针，一个指针为需要被覆盖的罗汉，另一个为要放置的罗汉，设置他们可以被覆盖的个数，如果可以被覆盖的个数为0，说明他们都已经被覆盖，需要看下一个物品是否可以被覆盖。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 1e9+5;
struct node{int w,v,num;//num:当前物品在显示在罗汉外面的个数，如果当前物品覆盖，前一个物品显示在外面的个数减少，当前物品显示在外面的个数增加bool operator < (const node & r) const{return w>r.w;}
}nod[N];
long long ans;
int n,m,k;int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>nod[i].w>>nod[i].v;nod[i].num=0;} sort(nod+1,nod+n+1);nod[0].w=2e9;nod[0].num=m;for(int l=0,i=1;i<=n;i++){//l为显示在外面物品的指针，i为要放置物品指针while(nod[i].v&&nod[l].w-nod[i].w>=k){//第i个物品可以放在第l个物品上int cur = min(nod[l].num,nod[i].v);//物品数量少于可放置的槽，就全部放物品，可放物品数量大于可放的槽，先把槽填满ans+=cur;nod[i].v-=cur;nod[i].num+=cur;//当前露在外面的个数增加nod[l].num-=cur;//覆盖物品的个数减少if(nod[l].num==0) l++;}}cout<<ans;return 0;
}这篇关于USACO 2023 December, SilverProblem 1. Bovine Acrobatics题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
