P4165 [SCOI2007]组队 推柿子+差分

题意：

题意

分析：

• 推柿子 ：

$A\times h-A\times mi{n}_h+B\times s-B\times mi{n}_s\le C$

我们发现有三个变量，所以最暴力的复杂度是$O(n^3)$的，那么我们考虑怎么优化

好吧，我不看题解也不是很会优化

我们将式子转化一下，然后会发现对于每一个人，$mi{n}_h$固定时，能取到的合法$mi{n}_s$是连续的

$$\frac{A\times (h-mi{n}_h)-C}{B}+s\le mi{n}_v\le s$$

前面一个限制是由式子转化得到的，后面的限制是题目要求，$mi{n}_s\le \forall s$

对于区间加的操作直接差分一下

代码：

#include<bits/stdc++.h>using namespace std;namespace zzc {const int maxn = 5005;long long h[maxn],s[maxn],num[10005],d[maxn];long long n,cnt=0,ans,a,b,c;void work(){ios::sync_with_stdio(false);cin>>n>>a>>b>>c;for(int i=1;i<=n;i++){cin>>h[i]>>s[i];d[i]=h[i];}sort(d+1,d+n+1);cnt=unique(d+1,d+n+1)-d-1;for(int i=1,l;i<=cnt;i++){memset(num,0,sizeof(num));for(int j=1;j<=n;j++){if(h[j]>=d[i]&&a*(h[j]-d[i])<=c){if(b==0) l=1;else l=max(1ll,s[j]-(c-a*(h[j]-d[i]))/b);num[l]++;num[s[j]+1]--;}}for(int j=1;j<=10000;j++) num[j]+=num[j-1];for(int j=1;j<=n;j++) ans=max(ans,num[s[j]]);}cout<<ans<<endl;}}int main() {zzc::work();return 0; }

总结

以上是生活随笔为你收集整理的P4165 [SCOI2007]组队 推柿子+差分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。