这题我写了两个二分函数。
BS借用的模板是找到第一个大于等于总价的商品下标,然后返回的是钻石价值和减去商品总价,通过遍历来得到最小的差值,注意遍历的最后一个数字的时候可能会返回负值,所以只有当返回值大于等于0才可以用来竞争最小差值。
得到了最小差值。BS2函数的模板是找到符合固定条件的商品下标,当然可能找不到,此时返回-1。
AC代码
#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>using namespace std;const int SUP = 100000000;
const int maxn = 100010;vector<pair<int,int> > ans;
int n,T;
int M[maxn];
int C[maxn];int getT(int begin,int end){return C[end]-C[begin]+M[begin];
}int BS(int begin,int l,int r){int mid,dif;while(l<r){mid = (l+r)/2;if(getT(begin,mid)>=T){r = mid;}else{l = mid+1;}}dif = getT(begin,l) - T;return dif;
} int BS2(int begin,int l,int r,int dif){int mid;while(l<=r){mid = (l+r)/2;if(getT(begin,mid)<T+dif){l = mid+1;}else if(getT(begin,mid)>T+dif){r = mid-1;}else return mid;}return -1;
}int main(){cin>>n>>T;C[0] = 0;for(int i=1;i<=n;i++){cin>>M[i];C[i] = C[i-1]+M[i];}int minDif = SUP;for(int i=1;i<=n;i++){int dif = BS(i,i,n);if(dif>=0){minDif = min(minDif,dif);}}
// printf("minDif = %d\n",minDif); for(int i=1;i<=n;i++){int j = BS2(i,i,n,minDif);if(j!=-1)printf("%d-%d\n",i,j);}return 0;
}