tracker2026.02.07相邻的糖果 贪心+双指针

那么我们可以想如果这个盒子里面的糖果的数目和超过了x个那肯定是要把超出的部分都减掉。而前面的盒子又会跟后面的盒子又组成新的一组。所以减掉后面的糖果会让下一组的总数减少所以我们肯定是优先减掉靠后的糖果。我在这里实现的时候就是说如果sumx就相应的减掉sum-x个。因为如果本身不大于x个而加入新的糖果之后整体大于x那么新进来的盒子肯定是够减的。这里用双指针维护如果不够m个那就是右指针右移。当算完了这一组m个之后左指针右移这样下一次循环的时候就会判断为不够m个右指针继续右移。纯享版#includebits/stdc.h using namespace std; #define int long long const int N 1e6100; int a[N]; int n,m,x; signed main() { cinnmx; for(int i 1 ; i n ; i)cina[i]; int l 0,r 0; int sum 0,cnt 0; while(r n) { while(r-l1 m){ r; suma[r]; if(sum x){ int res sum-x; cnt res;a[r]-res;sum-res; } } sum-a[l];l; } coutcntendl; return 0; }测试备注版#includebits/stdc.h using namespace std; #define int long long const int N 1e6100; int a[N]; int n,m,x; signed main() { cinnmx; for(int i 1 ; i n ; i)cina[i]; int l 0,r 0; int sum 0,cnt 0; //sum表示目前手里有的cnt表示需要拿掉的糖果 while(r n) { while(r-l1 m){ //如果不够的话就往后加 // coutr lendl; r; suma[r]; if(sum x){ int res sum-x;//超出的部分 // coutr resendl; // coutsum x resendl; cnt res;a[r]-res;sum-res; // 累加超出的部分并且让当前的减掉 } } // coutr lendl; sum-a[l];l; // 左指针右移并且减掉相应贡献 } // coutr lendl; // for(int i 1 ; i n ; i) // couta[i] \n[i n]; // coutr lendl; coutcntendl; return 0; }