类似还有一个题是二分,用区间来判断是否有解
这个爆long long 有点坑了
const int N = 1e2 + 10;LL n,tc,Tm;
LL a[N],b[N],c[N];bool check(LL mid)
{LL minx = max(0LL,mid + 1 - Tm),maxx = min(tc - 1LL,mid);//将y转为x的函数,此时判断x是否有解//枚举所有客户的需求,不断对x的范围取交集for (int i = 1;i <= n;i ++){//爆Long long// LL t1 = b[i] - a[i],t2 = c[i] - a[i] * tc - b[i] * (Tm - mid);// if (t1 == 0 && t2 < 0) return false; // else if (t1 > 0) maxx = min(maxx,(LL)floor(t2 / t1));// else if (t1 < 0) minx = max(minx,(LL)ceil(t2 / t1));double t1 = b[i] - a[i],t2 = c[i] - (double)a[i] * tc - (double)b[i] * (Tm - mid);if (t1 == 0 && t2 < 0) return false; else if (t1 > 0) maxx = min(maxx,(LL)floor(t2 / t1));else if (t1 < 0) minx = max(minx,(LL)ceil(t2 / t1));}return minx <= maxx;
}void solve()
{cin >> n >> tc >> Tm;for (int i = 1;i <= n;i ++) cin >> a[i] >> b[i] >> c[i];//二分总共升级多少LL l = -1,r = tc + Tm;while(l + 1 != r){LL mid = l + r >> 1;if (check(mid)) r = mid;else l = mid;}if (check(l)) cout << l << endl;else cout << r << endl;}