一道二分答案加前綴和

題目中已經暗示的很明顯了 “盡可能靠近” “ 最小值”
本題的主要坑點在于 long long 的使用

abs函數不支持long long !!!

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int MAXN=200005; long long read(){long long rv=0,fh=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') fh=-1;c=getchar();}while(c>='0'&&c<='9'){rv=(rv<<1)+(rv<<3)+c-'0';c=getchar();}return fh*rv; } int n,m,w[MAXN],v[MAXN],L[MAXN],R[MAXN]; long long S,T,num[MAXN],pre[MAXN],ans=1000000000000005; void chk(int x){T=0;memset(num,0,sizeof(num));memset(pre,0,sizeof(pre));for(int i=1;i<=n;i++){if(w[i]>=x){num[i]=num[i-1]+1;pre[i]=pre[i-1]+v[i];}else {num[i]=num[i-1];pre[i]=pre[i-1];}}for(int i=1;i<=m;i++){T+=(num[R[i]]-num[L[i]-1])*(pre[R[i]]-pre[L[i]-1]);}if(T>=S) ans=min(ans,T-S);else ans=min(ans,S-T);//注意最小值不一定在最后產生，而且最小值有可能會很大，一定要初始化一個很大的值 } int main(){freopen("in.txt","r",stdin);n=read();m=read();cin>>S;int l=100000007,r=0,mid=0;for(int i=1;i<=n;i++){w[i]=read();v[i]=read();l=min(l,w[i]);r=max(r,w[i]);}for(int i=1;i<=m;i++){L[i]=read();R[i]=read();}while(l<=r){mid=(l+r)>>1;chk(mid);if(T==S) break;if(T>S){l=mid+1;}else r=mid-1;}cout<<ans;fclose(stdin);return 0; }

轉載于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/7868359.html

總結

以上是生活随笔為你收集整理的洛谷 [P1314] 聪明的质检员（NOIP2011 D2T2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。