目录

C. Balanced Stone Heaps

P2440 木材加工

C. Balanced Stone Heaps

原题描述

 题意理解 

有n堆石头，第i堆有hi个石头，现定义如下操作：

1.从第3堆开始，到第n堆，每一堆都要执行一次。

2.对于第i堆石头，你可以选择一个数d(0<=3*d<=hi)，从第i堆移动d个石头到第i-1堆，再从第i堆移动2*d个石头到第i-2堆。

3.第i堆石头减少3*d个，第i-1堆增加d个，第i-2堆增加2*d个。

对于每一堆石头选择相同或不相同的d，使得所有操作结束后，最小堆中的石头数量最大。

题解

        初看此题的第一反应就是贪心，但是细看下去觉得是dp，因为你之前的选择会影响到后面的选择。但是我们不妨倒着想。

        我们假定所有的堆的石头数都大于x，i从第n堆开始到第3堆，将石头从第i堆移动到第i-1和i-2堆上去，这样我们每一次操作后，对于第i堆而言石头数量就已经确定下来了，所以我们保证第i堆剩下的石头大于x即可，因此我们的d取(hi‘-x)/3即可，值得注意的是这个hi‘是hi经过操作后得到的，但是d是不能过原始石头数量的，所以d取min(hi,(hi'-x))/3。如果x符合要求，每一个hi'-x肯定是大于0的，如果hi'<x，直接返回false即可。所有操作结束后第2堆和第1堆的石头都大于x，则该满足要求，返回true。

        我们通过二分查找来找到这个x即可，上面就是check函数的思路。

AC代码

/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define N 200001
int a[N],n;
bool check(int x){int b[N];_for(i,0,n-1) b[i]=a[i+1];for(int i=n-1;i>=2;i--){if(b[i]<x) return false;int d=min(a[i+1],b[i]-x)/3;b[i-1]+=d;b[i-2]+=2*d;}return b[1]>=x&&b[0]>=x;
}
int main(){int t;cin>>t;while(t--){cin>>n;_for(i,1,n) cin>>a[i];int l=0,r=*max_element(a+1,a+n+1);while(l<r){int mid=l+(r-l+1)/2;if(check(mid)) l=mid;else r=mid-1;}cout<<l<<endl;}return 0;
} 

第一道1600的题。 

P2440 木材加工

刚刚又写了一道洛谷的二分查找的题，也贴在这里吧。

二分答案特征挺明显的，类似于最小值的最大值，且解区间不是很大时，一般都是二分。

 这种简单的题我就不解释了,直接二分答案，然后check里面遍历数组看是否满足要求即可。

AC代码

/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define N 100001
int a[N],n,k;
bool check(int x){int temp=0;_for(i,1,n) temp+=a[i]/x; return temp>=k;
}
int main(){cin>>n>>k;_for(i,1,n) cin>>a[i];int l=1,r=*max_element(a+1,a+1+n),mid;while(l<r){mid=(l+r)/2;if(check(mid)) l=mid+1;else r=mid;}cout<<l-1<<endl;
}

记得l初始值为1，而不是0，否则会RE。

如果对你有帮助，可以点个赞。