題目鏈接：點擊查看

題目大意：給出一個n*n的矩陣，每個格子的權值為i*i+j*j+i*j+100000*(i-j)，求該矩陣中第m小的權值為多少

題目分析：這個題在選拔的時候給我整自閉了，看到n有5e4這么大，肯定是排除了暴力模擬的方法，那么我一開始打了個表找了一下n從1到10的規律，發現真的有規律，然后花了一個小時找到了規律把樣例過了，興致勃勃交了一發果不其然的WA掉了，就十分自閉了，完事之后想了一下，因為當n很小的時候，確實有規律，但是當n大了之后，也就是后面的100000*(i-j)開始起作用的時候，那么規律就不是那么簡單了，所以這毫無疑問。。不是一個規律題

那么正解該怎么做呢？正解是二分套二分，我們首先需要知道原理，然后就很好實現了，我們觀察一下這個方程，可以發現當j固定的時候，整個方程的值是隨著i遞增的，那么我們在外層的二分可以直接二分答案，這樣外層的二分結束后答案也就得到了，主要是內層該怎么處理呢？我們可以用nlogn的時間復雜度，來枚舉n個j，二分每一列j時的答案i，因為我們已經知道了當j固定的時候，函數值是隨i遞增的，所以我們可以在每一列都找出一個“中間點”，這個點前面的i都滿足cal(i,j)小于等于外層二分的答案，這個點后面的i都滿足cal(i,j)大于外層二分的答案，將枚舉的每個j所二分出來小于等于答案的i的個數加起來，就能求出來在外層二分的當前答案下，有多少個比該答案小的數的個數了，用這個數和一開始給出的m比較，不斷這樣循環就能求出答案來了

直接上代碼吧，總共是nlognlogn的復雜度，實現很簡單：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=(1<<11)+100;int n,m;LL cal(LL i,LL j) {return i*i+j*j+i*j+100000*(i-j); }int check(LL x) {int ans=0;for(int j=1;j<=n;j++)//枚舉j{int l=1;int r=n;int sum=0;while(l<=r)//二分i{int mid=l+r>>1;if(cal(mid,j)<=x)//若 二分的i 與 枚舉的j 所求出的答案小于等于 外層二分的答案 時更新{sum=mid;l=mid+1;}else{r=mid-1;}}ans+=sum;}return ans; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){scanf("%d%d",&n,&m);LL l=-inf;LL r=inf;LL ans;//記得都要開long longwhile(l<=r)//外層二分答案{LL mid=l+r>>1;if(check(mid)>=m){ans=mid;r=mid-1;}else{l=mid+1;}}printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的qduoj - WHY吃糖果(二分套二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

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