1824进击的奶牛整型数据二分[P1824 USACO05FEB] 进击的奶牛 Aggressive Cows G - 洛谷解题过程二分距离判断函数check(x)间距至少 x 时最多能放下多少头牛。排序坐标二分区间l1r最大坐标check(mid)满足能放下≥m 头牛说明距离 mid 可行尝试更大值ansmid,lmid1不满足则缩小距离rmid-1。适用场景求最小值的最大可能值代码实现//5303 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll n,m; vectorlla; bool check(ll x) { ll cnt1; ll heada[0]; for(ll i1;in;i) { if(a[i]-headx) { cnt; heada[i]; } } return cntm; } int main() { IOS cinnm; for(ll i0;in;i) { ll A; cinA; a.push_back(A); } sort(a.begin(),a.end()); ll l1,r0x3f3f3f3f; ll ans0; while(lr) { ll mid(lr)/2; if(check(mid)) { ansmax(mid,ans); lmid1; } else { rmid-1; } } coutansendl; // coutfixedsetprecision(x) ; return 0; }P1577切绳子浮点型数据二分P1577 切绳子 - 洛谷解题过程二分单段绳子长度check(x)统计能切出多少段长度≥x 的绳子。二分循环固定迭代 100 次替代整数边界判断保证精度满足段数≥k记录答案并向右二分找更长长度ansmid,lmid不满足则向左缩小长度rmid最后向下取整保留两位小数输出。适用场景答案为小数、对精度有要求的二分问题。代码实现//1577 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll n,k; vectordoublea; bool check(double x) { ll cnt0; for(ll i0;in;i) { cnt(ll)(a[i]/x); } return cntk; } int main() { IOS cinnk; double r0; for(ll i0;in;i) { double A; cinA; a.push_back(A); rmax(r,A); } // sort(a.begin(),a.end()); double l0; double ans0; for(ll i1;i100;i) { double mid(lr)/2; if(check(mid)) { ansmid; lmid; } else { rmid; } } ansfloor(ans*100)/100; coutfixedsetprecision(2)ansendl ; return 0; }整型二分 vs 浮点二分一、循环终止条件核心差异1. 整型二分整数区间离散区间边界是整数可以用l r循环靠mid±1收缩边界最终精准锁定整数答案。ll l1, r1e9; while(l r) { ll mid (l r) / 2; if(check(mid)) { ansmid; lmid1; // 可行往右找更大 } else rmid-1; // 不可行往左缩小 }原理整数点是有限离散值每次直接排除mid不会死循环。2. 浮点二分实数区间连续实数有无穷多个不能用lr无法精准等于边界标准写法固定循环 100 次100 次二分后精度远超题目要求的 1e-6/1e-2。double l0, rmax_len; for(int i1;i100;i) { double mid (l r) / 2; if(check(mid)) { ansmid; lmid; // 可行右边界移到mid } else rmid; // 不可行左边界移到mid } }原理实数区间不能mid±1只能不断缩小区间范围靠迭代保证精度。浮点存在浮点数精度丢失不能直接输出如切绳子需要向下取整保留两位小数ansfloor(ans*100)/100配合setprecision(2)输出。P1843奶牛晒衣服P1843 奶牛晒衣服 - 洛谷解题过程二分答案推荐效率更高二分总晾晒时间scheck(s)判断s时间内能否晒干所有衣服每件衣服自然风干s*a剩余水分需要烘干机统计所有衣服烘干总次数若总次数≤s 则时间 s 可行尝试更小时间ansmid,rmid-1不可行则增大时间lmid1。优先队列暴力每次取出含水量最大的衣服烘干 b 水分循环直到所有衣服自然风干即可代码实现//1843 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll n,a,b; ll mx,ti; int main() { IOS priority_queuellq; cinnab; for(ll i0;in;i) { ll x; cinx; q.push(x); } mxq.top(); q.pop(); while(mxti*a) { ti; mx-b; q.push(mx); mxq.top(); q.pop(); } couttiendl; return 0; }二分//1843 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll n,aa,b; //ll s; ll mx,ti; vectorlla; bool check(ll s) { ll sum0; for(ll i0;in;i) { if(a[i]s*aa) continue; ll rea[i]-s*aa; sum(reb-1)/b; if(sums) return false; } return sums; } int main() { IOS cinnaab; for(ll i0;in;i) { ll x; cinx; a.push_back(x); } sort(a.begin(),a.end()); ll l0,ra[n-1]; ll ans0; while(lr) { ll mid(lr)/2; if(check(mid)) { ansmid; rmid-1; } else { lmid1; } } coutansendl; return 0; }P1638逛画展P1638 逛画展 - 洛谷说明:滑动窗口解题过程用两个指针l窗口左边界、r窗口右边界维护一个动态区间右指针r不断向右扩张窗口把新画作纳入窗口统计窗口内画作种类数量kind当窗口集齐全部 m种画kind m说明当前区间合法持续收缩左指针l尽可能缩短区间长度每次收缩前更新最短区间答案左指针移出某类画且该画在窗口内数量变为 0 时种类数kind减一停止收缩继续右移r。代码实现//1843 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll n,m; int main() { IOS cinnm; vectorlla(n2); vectorllcnt(m2,0); for(int i1;in;i) { cina[i]; } ll l1; ll kind0; ll ansx0,ansy0; ll mincurLLONG_MAX; for(ll r1;rn;r) { if(cnt[a[r]]0) { kind; } cnt[a[r]]; while(kindm) { ll curr-l1; if(curmincur||(curmincurlansx)) { mincurcur; ansxl; ansyr; } cnt[a[l]]--; if(cnt[a[l]]0) kind--; l; } } coutansx ansyendl; return 0; }e IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#define ull unsigned long long#define fi first#define se secondusing namespace std;ll n,m;int main(){IOScinnm;vectora(n2);vectorcnt(m2,0);for(int i1;in;i){cina[i];}ll l1;ll kind0;ll ansx0,ansy0;ll mincurLLONG_MAX;for(ll r1;rn;r){if(cnt[a[r]]0){kind;}cnt[a[r]];while(kindm){ll curr-l1;if(curmincur||(curmincurlansx)){mincurcur;ansxl;ansyr;}cnt[a[l]]–;if(cnt[a[l]]0)kind–;l;}}coutansx ansyendl;return 0;}
)
)
