[C++知识库]【CF div2】B. Absent Remainder、C. Complex Market Analysis【二分答案】

B. Absent Remainder

传送门

题意：
n个不同的数，可以两两配对。
求出n/2对满足x%y的值不在数组内的。

题解：
我是弱智，纯思维。
找出最小的那个值，任何一个数对这个数求模绝对不会大于这个数的值，所以绝对不会出现在数组中。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
#define ll long long
#define sc scanf
#define pr printf
int a[maxn];
int main(){
     int t;cin>>t;
     while(t--){
     int n;cin>>n;
     int mmin=INT_MAX;
     for(int i=0;i<n;i++){
        cin>>a[i];
        mmin=min(mmin,a[i]);
     }
     int cnt=n/2;
     for(int i=0;i<n;i++){
        if(a[i]!=mmin){
            pr("%d %d\n",a[i],mmin);
            cnt--;
        }
        if(cnt==0)break;
     }
     }
     return 0;
}

C. Complex Market Analysis

传送门

题意：
在每一次下毒时开始，可持续k个时常，下一次下毒则会强制停止，进行新的毒药毒害。每秒毒害值为-1。血量为h，求最佳的k。

题解：
就是说，很明显的二分答案，h都1e18了，前几天才写了二分答案的题。
当时我呆了吧唧的看了一眼一个算法交流群，有人：【c？wf算法啊】。然而我没学过wf。开始迷茫。浪费了好一会时间。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+6;
#define ll long long
#define sc scanf
#define pr printf
#include<vector>
ll a[maxn];
ll c[maxn];
int n;ll h;
bool check(ll mid){
    ll sum=0;
    for(int i=0;i<n-1;i++){
        if(mid>c[i])sum+=c[i];
        else sum+=mid;
    }
    sum+=mid;
    if(sum>=h)return 1;
    else return 0;
}
int main()
{
    int t;cin>>t;
    while(t--){
       cin>>n>>h;
       for(int i=0;i<n;i++){
	   cin>>a[i];
	   if(i!=0)c[i-1]=a[i]-a[i-1];
	   }
       ll l=1,r=1e18;
       ll ret=r;ll mid;
       while(l<=r){
            mid=(l+r)/2;
        if(check(mid)){ret=mid;r=mid-1;}
        else l=mid+1;
       }
       pr("%lld\n",ret);
    }
    return 0;
}