前缀和和差分笔记一维前缀和示意图如下代码**核心公式sum[i]sum[i-1]a[i];计算前缀和的**#includebits/stdc.h using namespace std; const int N10000; #define ll long long int a[N],sum[N]; int main(){ cina[0]; sum[0]a[0]; for(int i1;inum;i){ cina[i]; sum[i]sum[i-1]a[i]; } }应用用于计算区间和公式为sum[R]-sum[L-1]计算第L位到第R位的区间和P8218 【深进1.例1】求区间和 - 洛谷二维前缀和示意图在写核心公式之前先明确几个概念什么是sum[x] [y]代码核心公式1.anssum[x2] [y2]-sum[x1-1] [y2]-sum[x2] [y1-1]sum[x1-1] [y1-1]怎么记首先混搭然后一行变一行就不变且x2不变最后减掉都变如x2不变则x1变变为x1-1sum[x2] [y2]-sum[x1-1] [y2]-sum[x2] [y1-1]-sum[x1-1] [y1-1]默写完毕sum[i] [j]sum[i-1] [j]sum[i] [j-1]-sum[i-1] [j-1]g[i] [j];左右都加顺便加自己减去重复的记得在那之前要写好你的三个条件if(!x1!y1) return sum[x2][y2]; // 如果起点在00则直接输出sum if(!x1) return sum[x2][y2]-sum[x2][y1-1]; if(!y1) return sum[x2][y2]-sum[x1-1][y2]; //口诀就是固定那个那个位置就不变如固定x1则x2不变y1变则需要减掉的就是sum[x2][y1-1]//二维前缀和 #include bits/stdc.h using namespace std; #define ll long long const int N 10000; int n 3, m 4; int g[3][4] {{1, 2, 6, 8}, {9, 6, 7, 3}, {5, 3, 2, 4} }; int sum[N][N]; void presum() { sum[0][0] g[0][0]; for (int i 1; i n; i) { sum[i][0] sum[i - 1][0] g[i][0];//第一列,固定列前缀和 } for (int i 1; i n; i) { sum[0][i] sum[0][i - 1] g[0][i]; //第一行固定行前缀和 } for (int i 1; i n; i) { for (int j 1; j m; j) { sum[i][j] g[i][j] sum[i][j - 1] sum[i - 1][j] - sum[i - 1][j - 1]; } } } int getsum(int x1, int y1, int x2, int y2) { if (!x1 !y1) return sum[x2][y2]; // 如果起点在00则直接输出sum if (!x1) return sum[x2][y2] - sum[x2][y1 - 1]; if (!y1) return sum[x2][y2] - sum[x1 - 1][y2]; return sum[x2][y2] - sum[x2][y1 - 1]-sum[x1-1][y2]sum[x1-1][y1-1]; } int main() { presum(); coutgetsum(1,1,2,2); return 0; }P1719 最大加权矩形 - 洛谷通过这道题我们能将这个过程再次简化//最大加权矩形 #includebits/stdc.h using namespace std; #define ll long long const int N10000; ll ansINT_MIN; ll g[N][N]; ll sum[N][N]; int main(){ int n; cinn; for(int i1;in;i){ for(int j1;jn;j){ cing[i][j]; sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]g[i][j]; } } for(int i1;in;i){ for(int j1;jn;j){ for(int ki;kn;k){ for(int qj;qn;q){ ansmax(sum[k][q]-sum[k][j-1]-sum[i-1][q]sum[i-1][j-1],ans); } } } } coutans; return 0; }一维差分差分可以看成前缀和的逆运算。不用差分的话每次操作都必须要循环一次时间复杂度比较高那么久简单啦每次操作我们就只需要操作两位数比如我操作【2,4】都加2就等价于d【2】v, d[41]-v为什么呢我们知道前缀和会怎么样会加上前面的数我的前面比原来大了2那么通过前缀和求出来的现在的值也就大了2那后面我不想改变怎么办简单在不想改变的那个位置减2不就抵消了吗?d为差分数组sumd为对差分数组求前缀和二分思想二分查找和二分答案其实本质都是二分思想二分思想的本质模版其实就是int bsearch(int l, int r) { //l为初值r为末尾值 //当左边和右边不相遇时 while (l r) { //求取中间用lr)/2 int mid (l r ) 1; //判断标准如果标准符合让其中一方缩小范围 if (check(mid)) r mid; else l mid 1; } //最后返回一个你想要的值左边一般是最小值右边一般是最大值 return l; }左边是最大的最小值右边是最小的最大值其实就是都一样的套路当两个指针不相遇的时候定义mid为l(r-1)1定义一个check函数如果可以在怎么样其中lmid1rmid还可以在后面加点其他思路的东西二分查找折半查找这里只讲他怎么用具体概念可以参考大佬的文章【算法笔记】二分查找 二分答案 超详细解析一篇让你搞懂二分-CSDN博客使用场景前提这个数据是有序的无需用sort变有序当问题需要查找元素是否存在或者求元素的坐标的时候可以使用方法其实是在划分区域如图为了找出红蓝的边界使用上述模版其check函数就可以判断他是蓝色还是红色然后如此循环即可找出一个红蓝边界mid的最终结果其实就是check函数的边界如check为红蓝判断函数则mid最后结果为红蓝边界l为蓝色r为红色check函数为是小于等于5l为最后一个小于等于5的数字mid为小于等于5的边界以此类推上述过程可以用代码完成但是如果只是为了查找就会比较简单直接用现有的函数即可1.如果你是想要查找是否存在使用binary_search()放回一个bool值2.查找第一个大于等于x的数组位置lower_bound(a.begin(),a.end(),x)3.查找第一个大于x的数组位置。upper_bound(a.begin(),a.end(),x)代码//二分查找 #includebits/stdc.h using namespace std; #define ll long long vectorinta{1,2,3,5,5,5,8,8,9,9}; //int binary(){ // int l-1,r10; // while(l1!r){ // int mfloor((lr)/2); // if(a[m]5) // lm; // else // rm; // } // return l; //} int main(){ // 返回一个bool值,查看这个元素是否存在 int ansbinary_search(a.begin(),a.end(),15);//若不存在返回 int ans1(lower_bound(a.begin(),a.end(),5)-a.begin()); int ans2(upper_bound(a.begin(),a.end(),5)-a.begin()); coutans ans1 ans2; return 0; }例题P1102 A-B 数对 - 洛谷灵活运用好lower_bound(第一个大于等于)和up_bound第一个大于我们用第一个大于减去第一个大于等于得到的数量不就是重复的的那一些2 3 3 3 3 3 4大于等于3 返回1大于3 返回6则可以算出3有6-15个//二分查找AB数对 #includebits/stdc.h using namespace std; #define ll long long ll a[200100]; int main(){ ll n,m,ans0; cinnm; for(int i0;in;i){ cina[i]; } sort(a,an); for(int i0;in;i){ ans(upper_bound(a,an,a[i]-m)-a)-(lower_bound(a,an,a[i]-m)-a); } coutans; return 0; }二分答案那什么是二分答案呢使用场景前提是这个区间是有序的无序必须想方法变有序对于一个问题它的答案属于一个区间当这个区间很大时暴力超时。如果这个区间有序我们则可以折半查找选定一个标准如果中间大于这个标准则答案在左边如果小于则在右边由此往复方法及其代码int bsearch(int l, int r) { //l为初值r为末尾值 //当左边和右边不相遇时 while (l r) { //求取中间用lr)/2 int mid (l r ) 1; //判断标准如果标准符合让其中一方缩小范围 if (check(mid)) r mid; else l mid 1; } //最后返回一个你想要的值左边一般是最小值右边一般是最大值 return l; }例题例题P1678 烦恼的高考志愿 - 洛谷其中两个简单样例1 100000 1000000 以下省略100000个0输出 100000000000429 517 7278 2729 3355 1555 595 7805 3741 3566 9466 1505 7419 9102 3236 3500 4592 307 9203 8880 8819 1480 5376 6897 3911 610 6376 4282 8522 5673 7206 5983 4695 8365 5799 9993 2575 4003 2377 2137 2968 982 466 9513 9234 1570 2079 7938 4516 806 4672 6900 4416 7508 2156 3963 5915 9896 8067 3708 6060 7315 1620 9070 7178 1542 209 6494 9107 978 7339 7319 5048 1870 6342 7869 7372 4688 741 5358 719 7100 1676 5659 4037 5825 6059 8794 7262 4350 5907 7882 4151 9194 7494 9752 4544 7377 3826 3268 2854 1437 3292 6055 9889 259 5139 6519 3088 6456 6733 8351 1097 9763 4016 1844 1019 2539 4562 6208 1603 4645 295 8685 9661 6699 3845 7790 6676 341 1878 8984 4395 5951 7551 5434 5977 6615 2091 5684 2100 4341 7353 4783 2864 5975 1944 7786 9326 8182 463 2650 8034 1239 8187 5704 8065 1817 826 7427 3106 6072 9140 2432 4514 574 5095 7696 6485 2495 833 2279 6703 2880 6002 1093 5494 4988 859 2153 260 9333 1949 1020 7153 7197 6866 6066 4860 5000 9588 620 6179 6913 2503 8188 3921 6325 6852 8031 4735 4672 1819 1998 5729 1984 2704 8201 1157 506 1132 3840 7487 9820 8205 9424 558 9379 331 1470 5587 9410 2497 2437 3112 3507 8898 699 3808 1333 2196 5951 314 7401 5283 2467 4700 5200 6907 8993 4824 6250 9202 3645 8580 9909 5606 563 2430 5730 8434 6382 8367 9938 2751 124 7395 3495 8416 3497 7283 751 1095 3803 1694 1320 4031 1561 8769 5781 673 5315 8278 827 2343 8053 3181 8397 8241 8737 5896 3446 5572 1141 6776 7396 1959 6151 6641 8670 7894 9428 6227 34 1464 7715 1358 7628 9449 6876 2166 5231 967 173 3547 2359 3367 9742 5978 2594 1400 449 2413 2888 4657 4748 5439 4892 3186 4717 1375 4152 8380 8038 9169 7861 6949 9061 7978 4176 9313 2485 8926 1561 2787 3925 6224 4608 8499 9501 8485 3971 4344 1961 9090 7110 129 1213 9159 5502 8918 5442 50 3197 2100 3126 3966 3934 8279 8750 3208 3623 5919 8977 6416 9065 5569 5199 5114 8893 7932 6667 4551 8814 5999 4848 9479 3617 9656 5513 8725 834 3010 1507 3 7018 7104 7550 169 3774 3796 4316 3729 6407 8540 7014 6464 3535 6400 8727 8131 7747 7011 6350 4455 7090 8353 5938 5833 2378 7865 9821 1087 3294 1723 4853 3500 3815 7995 4943 5297 5196 6646 8049 1674 5481 4178 1548 5438 6142 233 2028 4767 1452 5585 6046 3185 3919 4869 4886 1188 3349 8932 1797 5701 258 8231 115 237 5444 987 8003 2041 9922 385 548 8349 2435 1629 5438 1149 8945 8632 78 4811 4738 1085 829 5629 1096 9764 1927 8333 5213 9783 5575 1575 4872 8766 1440 6962 3793 5756 1017 716 7025 4732 1176 8533 9364 6778 8663 3759 7424 8289 1863 532 6235 2622 9246 6013 2733 4768 9963 2817 1578 6756 9838 6254 7343 1308 305 3455 8918 406 8693 8239 2571 6335 5367 7392 9398 6771 6768 448 2298 8180 6411 6568 4122 670 5873 2720 1679 4279 4046 1861 7566 2101 9415 909 2682 4685 4153 4139 7455 3688 142 626 9460 2357 8179 8681 6835 2980 5462 1822 9041 9887 7609 3187 4866 3145 3905 7033 2908 2548 8294 4758 1913 7742 6754 5985 1906 7389 9164 9400 1362 3952 4063 8116 3276 338 3543 7563 1103 7674 818 6427 9023 5926 4436 1258 3505 537 8634 6822 7986 9239 4839 9435 601 8538 5555 4898 1614 4460 3339 4641 9212 4282 6181 607 7823 3127 6878 3057 2077 4294 564 5731 5786 9872 6477 8864 5533 9878 524 5653 379 1188 7065 7666 6124 1665 6318 7250 530 8268 8231 7195 1608 7807 2406 920 9871 9008 5154 6774 6326 5612 6789 1875 1865 8467 7950 8781 2438 384 7758 4977 8832 9869 2327 9755 7596 6152 6460 20 676 5208 9756 9019 3644 486 7741 8561 739 1033 4435 5829 3352 4428 3396 968 9942 2552 5509 8257 4912 3456 5927 9093 589 6336 2953 2166 9288 4935 9554 269 5278 9337 1599 6136 2968 1104 4562 830 4037 4191 3872 4098 1845 5569 5659 4713 8083 9762 3986 9478 6027 784 7196 3985 7693 3839 5862 1201 2959 3536 9278 1882 9175 2288 3751 8208 6521 1620 4815 6406 660 7674 2707 4295 589 8924 3245 3721 6944 7685 9480 6896 6788 7365 4131 4289 8693 22 2088 6583 4622 1859 995 3998 8508 5856 1633 2880 8608 9817 7923 5547 7089 7987 6356 382 8254 9237 3247 8994 6047 9335 4764 6560 3068 9081 7108 4343 2110 3876 4265 2670 538 4964 7934 3687 5931 1279 419 1994 6227 6360 7393 2783 3060 3123 7103 200 6708 8682 4368 225 3328 6824 4863 715 3061 8569 8477 7467 9966 6178 5863 7674 559 4057 8866 8823 9709 8022 2961 4871 8415 9277 8126 770 207 806 7164 7410 9372 1284 4007 5606 5124 1921 6395 969 1189 7933 1013 7093 1942 5479 17 8709 1953 7547 5389 6813 8717 6976 6680 2451 5337 3247 5351 2494 7978 1095 6391 3229 2471 9632 294 7570 9671 5075 4509 6479 5697 2730 3298 47 8864 1185 2727 9917 3989 7475 1433 6592 1349 6461 7385 6931 2916 1289 4925 619 5637 1353 9313 2972 8303 8865 5923 8640 2168 2106 8590 5208 1276 1497 2348 2320 4420 3045 2443 1611 2427 6680 6139 6756 8287 8893 970 9291 8287 1863 9639 3617 8071 128 8212 9602 4016 7263 2594 4485 1737 1079 5251 6526 3124 5382 3668输出5865解答初版这道题主要是给我们指定的分数线数组A我们拿自己的成绩G在A中找到最后一个小于等于自己的那么对于本身不满意度最小的要么就是这个最后一个小于等于自己的要么就是下一个比自己大相差虽然不能确定但是你要知道二分答案就是一个划分区域的工具二刷后面的理解是不是要找最小那就二分是不是找本身最小那就本身入局作为边界则可以找出本身边界旁边的大小值#includebits/stdc.h using namespace std; #define ll long long //const int N100010; //int a[N]; //我们的模版二分答案是选出正确答案但是在实际做题的时候我们要结合实际情况 //来写check vectorint a; int ans(int k){ int sum0; int l0; int ra.size(); int mid; while(lr){ mid(lr)1; if(a[mid]k) lmid1; else rmid; } // 比第一个还低就没救了 if(ka[0]){ sumabs(a[0]-k); } // 否则就得设计算法 else summin(abs(a[l-1]-k),abs(a[l]-k)); return sum; } int main(){ int n,m,x; cinnm; // 高考各个学校分数线 for(int i0;in;i){ cinx; a.push_back(x); } sort(a.begin(),a.end()); ll t,ansum0; //对每个人的成绩进行遍历 for(int i0;im;i){ cint; ansumans(t); } coutansum; return 0; }记得开ll给ansum因为加起来可能会爆[P2678NOIP 2015 提高组] 跳石头 - 洛谷初版二分答案应该是在一个单调闭区间上进行的。所以当我们看到单调区间的时候我们就应该有个二分的想法了二分一般用来解决最优解问题。题目就是让我们找出一个最小值如果题目规定了有“最大值最小”或者“最小值最大”的东西那么这个东西应该就满足二分答案的有界性和单调性。所以讲了这么多这道题反正就是得用二分那我们应该怎么用呢我们知道二分的模版肯定是那样子int bsearch(int l, int r) { //l为初值r为末尾值 //当左边和右边不相遇时 while (l r) { //求取中间用lr)/2 int mid (l r ) 1; //判断标准如果标准符合让其中一方缩小范围 if (check(mid)) r mid; else l mid 1; } //最后返回一个你想要的值左边一般是最小值右边一般是最大值 return l; }想到二分其实最关键的就是我们要如何定义这个check首先我们看到的是他要移去石头其实本人一开始看着样例的时候呀就觉得这道题按他给的样例来的话移走两个不就是找出第三小的值吗所以其实为了更快查找我们是不是可以先设这个值为midlr/2反其道而行如果两者之间的距离大于这个值就说明可以如果小于就说明这里要被移走然后移走的数量最后对照是不是和题目给的移走m个相同相同则说明是mid这个其实是说明什么呢二分是可以寻找最小的最大值或者最大的最小值的我们这里其实就是符合条件的最大值**正好几这个思路什么的最大值移走后距离的最大值那么我们的mid就应该是距离**这里不开ll因为不求和其和也在int范围内#includebits/stdc.h using namespace std; #define ll long long int a[50110],l,n,m; bool check(int d){ int cnt0,pos0;//记录一下被移走了多少石头,pos为当前位置 for(int i1;in;i){ if(a[i]-posd)//这一步说明是在跳跃 cnt;//略过则直接过 else posa[i];//跳过就存储位置 } return cntm; } int main(){ cinlnm; for(int i1;in;i){ cina[i]; } a[n]l; int l11,rl,mid,ans-1; while(l1r){ mid(l1r)/2; if(check(mid)){ l1mid1; ansmid; }else{ rmid-1; } } coutans; return 0; }二刷理解 是不是在找距离的最大值那就距离入局找出这个距离的边界check函数变复杂了check函数一定是以距离为接收值的但是如何判断这个接收值呢举个例子就知道我们的接收值太大导致我们的cnt变化了题目又给了cnt具体值所以便可利用他来作为限制条件
前缀和和差分笔记一维前缀和示意图如下代码**核心公式sum[i]sum[i-1]a[i];计算前缀和的**#includebits/stdc.h using namespace std; const int N10000; #define ll long long int a[N],sum[N]; int main(){ cina[0]; sum[0]a[0]; for(int i1;inum;i){ cina[i]; sum[i]sum[i-1]a[i]; } }应用用于计算区间和公式为sum[R]-sum[L-1]计算第L位到第R位的区间和P8218 【深进1.例1】求区间和 - 洛谷二维前缀和示意图在写核心公式之前先明确几个概念什么是sum[x] [y]代码核心公式1.anssum[x2] [y2]-sum[x1-1] [y2]-sum[x2] [y1-1]sum[x1-1] [y1-1]怎么记首先混搭然后一行变一行就不变且x2不变最后减掉都变如x2不变则x1变变为x1-1sum[x2] [y2]-sum[x1-1] [y2]-sum[x2] [y1-1]-sum[x1-1] [y1-1]默写完毕sum[i] [j]sum[i-1] [j]sum[i] [j-1]-sum[i-1] [j-1]g[i] [j];左右都加顺便加自己减去重复的记得在那之前要写好你的三个条件if(!x1!y1) return sum[x2][y2]; // 如果起点在00则直接输出sum if(!x1) return sum[x2][y2]-sum[x2][y1-1]; if(!y1) return sum[x2][y2]-sum[x1-1][y2]; //口诀就是固定那个那个位置就不变如固定x1则x2不变y1变则需要减掉的就是sum[x2][y1-1]//二维前缀和 #include bits/stdc.h using namespace std; #define ll long long const int N 10000; int n 3, m 4; int g[3][4] {{1, 2, 6, 8}, {9, 6, 7, 3}, {5, 3, 2, 4} }; int sum[N][N]; void presum() { sum[0][0] g[0][0]; for (int i 1; i n; i) { sum[i][0] sum[i - 1][0] g[i][0];//第一列,固定列前缀和 } for (int i 1; i n; i) { sum[0][i] sum[0][i - 1] g[0][i]; //第一行固定行前缀和 } for (int i 1; i n; i) { for (int j 1; j m; j) { sum[i][j] g[i][j] sum[i][j - 1] sum[i - 1][j] - sum[i - 1][j - 1]; } } } int getsum(int x1, int y1, int x2, int y2) { if (!x1 !y1) return sum[x2][y2]; // 如果起点在00则直接输出sum if (!x1) return sum[x2][y2] - sum[x2][y1 - 1]; if (!y1) return sum[x2][y2] - sum[x1 - 1][y2]; return sum[x2][y2] - sum[x2][y1 - 1]-sum[x1-1][y2]sum[x1-1][y1-1]; } int main() { presum(); coutgetsum(1,1,2,2); return 0; }P1719 最大加权矩形 - 洛谷通过这道题我们能将这个过程再次简化//最大加权矩形 #includebits/stdc.h using namespace std; #define ll long long const int N10000; ll ansINT_MIN; ll g[N][N]; ll sum[N][N]; int main(){ int n; cinn; for(int i1;in;i){ for(int j1;jn;j){ cing[i][j]; sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]g[i][j]; } } for(int i1;in;i){ for(int j1;jn;j){ for(int ki;kn;k){ for(int qj;qn;q){ ansmax(sum[k][q]-sum[k][j-1]-sum[i-1][q]sum[i-1][j-1],ans); } } } } coutans; return 0; }一维差分差分可以看成前缀和的逆运算。不用差分的话每次操作都必须要循环一次时间复杂度比较高那么久简单啦每次操作我们就只需要操作两位数比如我操作【2,4】都加2就等价于d【2】v, d[41]-v为什么呢我们知道前缀和会怎么样会加上前面的数我的前面比原来大了2那么通过前缀和求出来的现在的值也就大了2那后面我不想改变怎么办简单在不想改变的那个位置减2不就抵消了吗?d为差分数组sumd为对差分数组求前缀和二分思想二分查找和二分答案其实本质都是二分思想二分思想的本质模版其实就是int bsearch(int l, int r) { //l为初值r为末尾值 //当左边和右边不相遇时 while (l r) { //求取中间用lr)/2 int mid (l r ) 1; //判断标准如果标准符合让其中一方缩小范围 if (check(mid)) r mid; else l mid 1; } //最后返回一个你想要的值左边一般是最小值右边一般是最大值 return l; }左边是最大的最小值右边是最小的最大值其实就是都一样的套路当两个指针不相遇的时候定义mid为l(r-1)1定义一个check函数如果可以在怎么样其中lmid1rmid还可以在后面加点其他思路的东西二分查找折半查找这里只讲他怎么用具体概念可以参考大佬的文章【算法笔记】二分查找 二分答案 超详细解析一篇让你搞懂二分-CSDN博客使用场景前提这个数据是有序的无需用sort变有序当问题需要查找元素是否存在或者求元素的坐标的时候可以使用方法其实是在划分区域如图为了找出红蓝的边界使用上述模版其check函数就可以判断他是蓝色还是红色然后如此循环即可找出一个红蓝边界mid的最终结果其实就是check函数的边界如check为红蓝判断函数则mid最后结果为红蓝边界l为蓝色r为红色check函数为是小于等于5l为最后一个小于等于5的数字mid为小于等于5的边界以此类推上述过程可以用代码完成但是如果只是为了查找就会比较简单直接用现有的函数即可1.如果你是想要查找是否存在使用binary_search()放回一个bool值2.查找第一个大于等于x的数组位置lower_bound(a.begin(),a.end(),x)3.查找第一个大于x的数组位置。upper_bound(a.begin(),a.end(),x)代码//二分查找 #includebits/stdc.h using namespace std; #define ll long long vectorinta{1,2,3,5,5,5,8,8,9,9}; //int binary(){ // int l-1,r10; // while(l1!r){ // int mfloor((lr)/2); // if(a[m]5) // lm; // else // rm; // } // return l; //} int main(){ // 返回一个bool值,查看这个元素是否存在 int ansbinary_search(a.begin(),a.end(),15);//若不存在返回 int ans1(lower_bound(a.begin(),a.end(),5)-a.begin()); int ans2(upper_bound(a.begin(),a.end(),5)-a.begin()); coutans ans1 ans2; return 0; }例题P1102 A-B 数对 - 洛谷灵活运用好lower_bound(第一个大于等于)和up_bound第一个大于我们用第一个大于减去第一个大于等于得到的数量不就是重复的的那一些2 3 3 3 3 3 4大于等于3 返回1大于3 返回6则可以算出3有6-15个//二分查找AB数对 #includebits/stdc.h using namespace std; #define ll long long ll a[200100]; int main(){ ll n,m,ans0; cinnm; for(int i0;in;i){ cina[i]; } sort(a,an); for(int i0;in;i){ ans(upper_bound(a,an,a[i]-m)-a)-(lower_bound(a,an,a[i]-m)-a); } coutans; return 0; }二分答案那什么是二分答案呢使用场景前提是这个区间是有序的无序必须想方法变有序对于一个问题它的答案属于一个区间当这个区间很大时暴力超时。如果这个区间有序我们则可以折半查找选定一个标准如果中间大于这个标准则答案在左边如果小于则在右边由此往复方法及其代码int bsearch(int l, int r) { //l为初值r为末尾值 //当左边和右边不相遇时 while (l r) { //求取中间用lr)/2 int mid (l r ) 1; //判断标准如果标准符合让其中一方缩小范围 if (check(mid)) r mid; else l mid 1; } //最后返回一个你想要的值左边一般是最小值右边一般是最大值 return l; }例题例题P1678 烦恼的高考志愿 - 洛谷其中两个简单样例1 100000 1000000 以下省略100000个0输出 100000000000429 517 7278 2729 3355 1555 595 7805 3741 3566 9466 1505 7419 9102 3236 3500 4592 307 9203 8880 8819 1480 5376 6897 3911 610 6376 4282 8522 5673 7206 5983 4695 8365 5799 9993 2575 4003 2377 2137 2968 982 466 9513 9234 1570 2079 7938 4516 806 4672 6900 4416 7508 2156 3963 5915 9896 8067 3708 6060 7315 1620 9070 7178 1542 209 6494 9107 978 7339 7319 5048 1870 6342 7869 7372 4688 741 5358 719 7100 1676 5659 4037 5825 6059 8794 7262 4350 5907 7882 4151 9194 7494 9752 4544 7377 3826 3268 2854 1437 3292 6055 9889 259 5139 6519 3088 6456 6733 8351 1097 9763 4016 1844 1019 2539 4562 6208 1603 4645 295 8685 9661 6699 3845 7790 6676 341 1878 8984 4395 5951 7551 5434 5977 6615 2091 5684 2100 4341 7353 4783 2864 5975 1944 7786 9326 8182 463 2650 8034 1239 8187 5704 8065 1817 826 7427 3106 6072 9140 2432 4514 574 5095 7696 6485 2495 833 2279 6703 2880 6002 1093 5494 4988 859 2153 260 9333 1949 1020 7153 7197 6866 6066 4860 5000 9588 620 6179 6913 2503 8188 3921 6325 6852 8031 4735 4672 1819 1998 5729 1984 2704 8201 1157 506 1132 3840 7487 9820 8205 9424 558 9379 331 1470 5587 9410 2497 2437 3112 3507 8898 699 3808 1333 2196 5951 314 7401 5283 2467 4700 5200 6907 8993 4824 6250 9202 3645 8580 9909 5606 563 2430 5730 8434 6382 8367 9938 2751 124 7395 3495 8416 3497 7283 751 1095 3803 1694 1320 4031 1561 8769 5781 673 5315 8278 827 2343 8053 3181 8397 8241 8737 5896 3446 5572 1141 6776 7396 1959 6151 6641 8670 7894 9428 6227 34 1464 7715 1358 7628 9449 6876 2166 5231 967 173 3547 2359 3367 9742 5978 2594 1400 449 2413 2888 4657 4748 5439 4892 3186 4717 1375 4152 8380 8038 9169 7861 6949 9061 7978 4176 9313 2485 8926 1561 2787 3925 6224 4608 8499 9501 8485 3971 4344 1961 9090 7110 129 1213 9159 5502 8918 5442 50 3197 2100 3126 3966 3934 8279 8750 3208 3623 5919 8977 6416 9065 5569 5199 5114 8893 7932 6667 4551 8814 5999 4848 9479 3617 9656 5513 8725 834 3010 1507 3 7018 7104 7550 169 3774 3796 4316 3729 6407 8540 7014 6464 3535 6400 8727 8131 7747 7011 6350 4455 7090 8353 5938 5833 2378 7865 9821 1087 3294 1723 4853 3500 3815 7995 4943 5297 5196 6646 8049 1674 5481 4178 1548 5438 6142 233 2028 4767 1452 5585 6046 3185 3919 4869 4886 1188 3349 8932 1797 5701 258 8231 115 237 5444 987 8003 2041 9922 385 548 8349 2435 1629 5438 1149 8945 8632 78 4811 4738 1085 829 5629 1096 9764 1927 8333 5213 9783 5575 1575 4872 8766 1440 6962 3793 5756 1017 716 7025 4732 1176 8533 9364 6778 8663 3759 7424 8289 1863 532 6235 2622 9246 6013 2733 4768 9963 2817 1578 6756 9838 6254 7343 1308 305 3455 8918 406 8693 8239 2571 6335 5367 7392 9398 6771 6768 448 2298 8180 6411 6568 4122 670 5873 2720 1679 4279 4046 1861 7566 2101 9415 909 2682 4685 4153 4139 7455 3688 142 626 9460 2357 8179 8681 6835 2980 5462 1822 9041 9887 7609 3187 4866 3145 3905 7033 2908 2548 8294 4758 1913 7742 6754 5985 1906 7389 9164 9400 1362 3952 4063 8116 3276 338 3543 7563 1103 7674 818 6427 9023 5926 4436 1258 3505 537 8634 6822 7986 9239 4839 9435 601 8538 5555 4898 1614 4460 3339 4641 9212 4282 6181 607 7823 3127 6878 3057 2077 4294 564 5731 5786 9872 6477 8864 5533 9878 524 5653 379 1188 7065 7666 6124 1665 6318 7250 530 8268 8231 7195 1608 7807 2406 920 9871 9008 5154 6774 6326 5612 6789 1875 1865 8467 7950 8781 2438 384 7758 4977 8832 9869 2327 9755 7596 6152 6460 20 676 5208 9756 9019 3644 486 7741 8561 739 1033 4435 5829 3352 4428 3396 968 9942 2552 5509 8257 4912 3456 5927 9093 589 6336 2953 2166 9288 4935 9554 269 5278 9337 1599 6136 2968 1104 4562 830 4037 4191 3872 4098 1845 5569 5659 4713 8083 9762 3986 9478 6027 784 7196 3985 7693 3839 5862 1201 2959 3536 9278 1882 9175 2288 3751 8208 6521 1620 4815 6406 660 7674 2707 4295 589 8924 3245 3721 6944 7685 9480 6896 6788 7365 4131 4289 8693 22 2088 6583 4622 1859 995 3998 8508 5856 1633 2880 8608 9817 7923 5547 7089 7987 6356 382 8254 9237 3247 8994 6047 9335 4764 6560 3068 9081 7108 4343 2110 3876 4265 2670 538 4964 7934 3687 5931 1279 419 1994 6227 6360 7393 2783 3060 3123 7103 200 6708 8682 4368 225 3328 6824 4863 715 3061 8569 8477 7467 9966 6178 5863 7674 559 4057 8866 8823 9709 8022 2961 4871 8415 9277 8126 770 207 806 7164 7410 9372 1284 4007 5606 5124 1921 6395 969 1189 7933 1013 7093 1942 5479 17 8709 1953 7547 5389 6813 8717 6976 6680 2451 5337 3247 5351 2494 7978 1095 6391 3229 2471 9632 294 7570 9671 5075 4509 6479 5697 2730 3298 47 8864 1185 2727 9917 3989 7475 1433 6592 1349 6461 7385 6931 2916 1289 4925 619 5637 1353 9313 2972 8303 8865 5923 8640 2168 2106 8590 5208 1276 1497 2348 2320 4420 3045 2443 1611 2427 6680 6139 6756 8287 8893 970 9291 8287 1863 9639 3617 8071 128 8212 9602 4016 7263 2594 4485 1737 1079 5251 6526 3124 5382 3668输出5865解答初版这道题主要是给我们指定的分数线数组A我们拿自己的成绩G在A中找到最后一个小于等于自己的那么对于本身不满意度最小的要么就是这个最后一个小于等于自己的要么就是下一个比自己大相差虽然不能确定但是你要知道二分答案就是一个划分区域的工具二刷后面的理解是不是要找最小那就二分是不是找本身最小那就本身入局作为边界则可以找出本身边界旁边的大小值#includebits/stdc.h using namespace std; #define ll long long //const int N100010; //int a[N]; //我们的模版二分答案是选出正确答案但是在实际做题的时候我们要结合实际情况 //来写check vectorint a; int ans(int k){ int sum0; int l0; int ra.size(); int mid; while(lr){ mid(lr)1; if(a[mid]k) lmid1; else rmid; } // 比第一个还低就没救了 if(ka[0]){ sumabs(a[0]-k); } // 否则就得设计算法 else summin(abs(a[l-1]-k),abs(a[l]-k)); return sum; } int main(){ int n,m,x; cinnm; // 高考各个学校分数线 for(int i0;in;i){ cinx; a.push_back(x); } sort(a.begin(),a.end()); ll t,ansum0; //对每个人的成绩进行遍历 for(int i0;im;i){ cint; ansumans(t); } coutansum; return 0; }记得开ll给ansum因为加起来可能会爆[P2678NOIP 2015 提高组] 跳石头 - 洛谷初版二分答案应该是在一个单调闭区间上进行的。所以当我们看到单调区间的时候我们就应该有个二分的想法了二分一般用来解决最优解问题。题目就是让我们找出一个最小值如果题目规定了有“最大值最小”或者“最小值最大”的东西那么这个东西应该就满足二分答案的有界性和单调性。所以讲了这么多这道题反正就是得用二分那我们应该怎么用呢我们知道二分的模版肯定是那样子int bsearch(int l, int r) { //l为初值r为末尾值 //当左边和右边不相遇时 while (l r) { //求取中间用lr)/2 int mid (l r ) 1; //判断标准如果标准符合让其中一方缩小范围 if (check(mid)) r mid; else l mid 1; } //最后返回一个你想要的值左边一般是最小值右边一般是最大值 return l; }想到二分其实最关键的就是我们要如何定义这个check首先我们看到的是他要移去石头其实本人一开始看着样例的时候呀就觉得这道题按他给的样例来的话移走两个不就是找出第三小的值吗所以其实为了更快查找我们是不是可以先设这个值为midlr/2反其道而行如果两者之间的距离大于这个值就说明可以如果小于就说明这里要被移走然后移走的数量最后对照是不是和题目给的移走m个相同相同则说明是mid这个其实是说明什么呢二分是可以寻找最小的最大值或者最大的最小值的我们这里其实就是符合条件的最大值**正好几这个思路什么的最大值移走后距离的最大值那么我们的mid就应该是距离**这里不开ll因为不求和其和也在int范围内#includebits/stdc.h using namespace std; #define ll long long int a[50110],l,n,m; bool check(int d){ int cnt0,pos0;//记录一下被移走了多少石头,pos为当前位置 for(int i1;in;i){ if(a[i]-posd)//这一步说明是在跳跃 cnt;//略过则直接过 else posa[i];//跳过就存储位置 } return cntm; } int main(){ cinlnm; for(int i1;in;i){ cina[i]; } a[n]l; int l11,rl,mid,ans-1; while(l1r){ mid(l1r)/2; if(check(mid)){ l1mid1; ansmid; }else{ rmid-1; } } coutans; return 0; }二刷理解 是不是在找距离的最大值那就距离入局找出这个距离的边界check函数变复杂了check函数一定是以距离为接收值的但是如何判断这个接收值呢举个例子就知道我们的接收值太大导致我们的cnt变化了题目又给了cnt具体值所以便可利用他来作为限制条件
