acwing-寒假每日一题

本文主要是介绍acwing-寒假每日一题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二分

1.技能升级

#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
int n,m;
int res=0;
int ans;
int result;
pair<int,int> a[100020];
int check(int mid){int cnt=0;for(int i=0;i<n;i++){if(a[i].first>mid){cnt+=ceil((double)(a[i].first-mid)/(a[i].second));}}return cnt<=m;
}
int sum(int a,int c,int b){int m=a-b*(c-1);return (m+a)*c>>1;
}
signed main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i].first>>a[i].second;}int l=0,r=1e6+10;while(l<r){int mid=l+r>>1;if(check(mid)){r=mid;}else{l=mid+1;}}result=m;for(int i=0;i<n;i++){//先求次数在求和if(a[i].first>l){ans=ceil((double)(a[i].first-l)/(a[i].second));result-=ans;res+=sum(a[i].first,ans,a[i].second);}}cout<<res+result*l;return 0;
}

对于浮点数，向上取整ceil，向下取整floor，四舍五入round
二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

yxc版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。C++ 代码模板：
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

yxc版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。C++ 代码模板：
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

这篇关于acwing-寒假每日一题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---