503. 借教室 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+7; // 根据实际需求设置合适的大小
int n, m; // 天数和订单的数量
int a[N];
int d[N], s[N], t[N];
int dd[N]; // 差分数组bool check(int mid) { // 到第mid个订单是否可以满足条件memset(dd, 0, sizeof(dd)); // 初始化差分数组为0
//差分数组dd的含义是每天新增或减少的订单数量。对于第i天，dd[i]表示第i天新增的订单数量减去前一天完成的订单数量。因此，差分数组的初始化应该为0    for (int i = 1; i <= mid; i++) {dd[s[i]] += d[i];//第s[i]天起开始需要d[i]个桌子dd[t[i] + 1] -= d[i];}int sum = 0;for (int i = 1; i <= n; i++) {sum += dd[i];//其实sum也就代表了每一天的需要的教室数量，因为差分求和就是a[i] if (a[i] < sum) return false; // 在前面就不行了}return true;
}
//因为订单时有顺序的所以这是有二段性的
void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= m; i++) {cin >> 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个订单都能满足else r = mid - 1;}if (r == m)cout << 0 << '\n';elsecout << -1 <<'\n'<< r + 1 << '\n';
}signed main() {int t = 1;while (t--) solve();return 0;
}

 1227. 分巧克力 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+7;
int n,k;
int h[N],w[N];
//mid是问的输出的答案 在return时候的条件尽量要与题目中的别的变量扯上关系
bool check(int mid){//表示巧克力的最大边长 int cnt=0;for(int i=1;i<=n;i++){//对于第i个巧克力 cnt+=(h[i]/mid)*(w[i]/mid);//长上能分出来的份数+宽上能分出来的份数}if(cnt>=k)return true;else return false;
}
void solve() {cin>>n>>k;//n个巧克力 分出来k块  邱最大边长 for(int i=1;i<=n;i++){cin>>h[i]>>w[i];}int l=0,r=max(*max_element(h+1,h+n+1),*max_element(w+1,w+n+1)) ;while(l<r){int mid=(l+r+1)>>1;if(check(mid))l=mid;else r=mid-1;}cout<<r;
}signed main() {int t = 1;while (t--) solve();return 0;
}