Ac503 借教室

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int n,m;
int s[N],t[N],d[N],w[N];
ll b[N];

bool check(int mid){
    memset(b,0,sizeof b);
    for(int i=1;i<=mid;i++){
        b[s[i]] += d[i];
        b[t[i]+1] -= d[i];
    }
    for(int i=1;i<=n;i++){
        b[i] += b[i - 1];
        if(b[i] > w[i])return false;
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);
    int l = 0,r = m;
    while(l<r){
        int mid = l + r + 1 >> 1;
        if(check(mid))l = mid;//mid在[1,k]
        else r = mid -1;//mid在[k+1,m]
    }
    if(r==m)puts("0");
    else printf("-1\n%d",r+1);
    return 0;
}

题目让求最后一个无法满足的订单数，设k为最后一个能满足的订单，[1,k]是能满足的订单数,[k+1,m]是不能满足的订单;
利用差分的性质，实时算出二分的订单，存到数组里，对天数进行遍历，逆运算前缀和得出真实数组，看是否超过了可分配的数量;

Ac1227 分巧克力

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,k;
int h[N],w[N];

bool check(int mid){
    ll res = 0;//注意开下ll,1e5大块每块切1e5块有可能超1e9
    for(int i=1;i<=n;i++){
        res += h[i]/mid * (w[i]/mid);
        if(res>=k)return true;
    }
    return false;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d%d",&h[i],&w[i]);
    int l = 1,r = 1e5;
    while(l<r){
        int mid = l + r + 1 >> 1;
        if(check(mid))l = mid;//mid[1,k]
        else r = mid - 1;//,mid在[k+1,len]
    }
    printf("%d",r);
    return 0;
}

题目让求能分的最大边长,设巧克力被分的最大边长为k,随边长的增长，块数在下降，[1,k]是可分的区间,[k+1,len]是不可分的区间;
对其二分出来能否满足块数大于k的最佳方案,长宽分别除二分的边长向下取整再想乘即该块切出的块数，遍历所有的巧克力对切出块数做累加，判断能否满足;

Ac5407 管道

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
const int N = 1e5+10;

int n,len;
PII p[N],q[N];

bool check(int mid){
    int cnt = 0;
    for(int i=0;i<n;i++){
        if(mid>=p[i].y){
            int t = mid - p[i].y;
            q[cnt++] = {max(1,p[i].x-t),min((ll)p[i].x+t,(ll)len)};
        }
    }
    sort(q,q+cnt);
    int st = -1,ed = -1;
    for(int i=0;i<cnt;i++){
        if(q[i].x <= ed + 1)ed = max(ed,q[i].y);
        else st = q[i].x,ed = q[i].y;
    }
    return st == 1&& ed == len;
}

int main(){
    scanf("%d%d",&n,&len);
    for(int i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);
    ll l = 0,r =2e9;//最大时间2e9-1时间和管道位置同为最大
    while(l<r){
        ll mid = l + r >>1;
        if(check(mid))r = mid;//mid在[k,2e9]
        else l = mid + 1;//mid在[0,k-1]
    }
    printf("%lld",r);
    return 0;
}

题目要求管道充满水的最短时间，设充满管道的最短时间为k，随时间的增长水的蔓延数也是单调递增的[0,k-1]是不能充满的区间,[k,2e9]是可以充满的区间;
水的蔓延数是时间t,算出所有二分时间之前的打开阀门,用键值对记录下来每个的左右区间,对左端点进行排序,能蔓延利用区间合并,算出总区间是否等于管长;

Ac4656 技能升级

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6+10;

int n,m;
int a[N],b[N];

bool check(int mid){
    ll res=0;
    for(int i=0;i<n;i++){
        if(a[i]>=mid)
        res+=(a[i]-mid)/b[i]+1;
    }
    return res>=m;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d%d",&a[i],&b[i]);

    int l=0,r=1e6;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    ll res=0,cnt=0;
    for(int  i=0;i<n;i++){
        if(a[i]>=r){
            int c=(a[i]-r)/b[i]+1;
            int end=a[i]-(c-1)*b[i];
            cnt+=c;
            res+=(ll)(a[i]+end)*c/2;
        }
    }
    printf("%lld\n",res-(cnt-m)*r);
    return 0;
}

该题要求最高能提升的攻击力是多少，先保证正确再进行优化，枚举所有技能攻击力，从大到小进行排序，取前m个即为可提升的最大攻击力;
设x为从大到小第m个数，那么大于等于x的个数一定大于等于x个，大于x+1的个数一定小于m个，二分出满足条件的第m个数;
再利用等差数列求和公式遍历所有技能，算出总攻击力，同时统计项数，因为第m个数有可能恰好有多个

Ac4956 冶炼金属

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    int v_min = 1, v_max = 1e9;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v_min = max(v_min, a / (b + 1) + 1);
        v_max = min(v_max, a / b);
    }

    printf("%d %d\n", v_min, v_max);
    return 0;
}

题目要求转换效率的最大和最小值,能够冶炼出b个，但是冶炼不出b+1个，所以a大于等于bv，a小于（b+1）v，可以推导出来最小值和最大值，因为无法满足最小的那个，所以还要+1，遍历一下就ok了;

Ac102 最佳牛围栏

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e5+10;

int n,m;
int cows[N];
double sum[N];

bool check(double avg)
{
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+cows[i]-avg;

    double minv = 0;
    for(int i=0,j=m;j<=n;i++,j++){
        minv=min(minv,sum[i]);
        if(sum[j]>=minv)return true;
    }
    return false;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&cows[i]);
    double l=0,r=2000;
    while(r-l>1e-5){
        double mid = (l+r)/2;
        if(check(mid))l = mid;
        else r = mid;
    }
    printf("%d\n",int(r*1000));

    return 0;
}

该题要求最大平均值，使用浮点二分进行查找平均值，用前缀和求连续子序列，判断存不存在sum[j]-sum[i]>=0;

Ac562 壁画

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 5e6+10;

int n;
int s[N];
char str[N];

int main(){
    int T;
    scanf("%d",&T);

    for(int cases = 1;cases <= T;cases++){
        scanf("%d",&n);
        scanf("%s",str+1);
        for(int i=1;i<=n;i++){
            s[i] = s[i-1] + str[i]-'0';
        }
        int res = 0,m = (n+1)/2;
        for(int i = m;i <= n;i++){
            res = max(res,s[i] - s[i - m]);
        }
        printf("Case #%d: %d\n",cases,res);
    }
    return 0;
}

该题要求美观分的最大值，墙只能从两边坏，因为是先画再坏，所以最后一定是n/2上取整个墙被画上了，其余墙坏掉了，遍历每一段连续子区间用前缀和算出美观值选出最大的;

Ac1230 K倍子区间

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;
const int N = 1e5+10;

int n,k;
ll s[N];
int cnt[N];

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        s[i] += s[i-1];
    }

    ll res = 0;
    cnt[0]++;
    for(int i=1;i<=n;i++){
        res += cnt[s[i]%k];
        cnt[s[i]%k]++;
    } 
    printf("%lld\n",res);
    return 0;
}

题目求k的倍数的个数，前缀和算出所有数，再利用hash数组储存，遍历所有数，得到K倍区间的个数