admin管理员组

文章数量:1130349

QLU

欢迎大家来做QLU_ACM寒假组织的专题训练🎈
本周专题关于 暴力、排序、贪心、二分

比赛链接 [密码2021]

专题目录

    • 一、暴力
      • A.水仙花数 (输入到文末)
      • B.求数列的和
      • C.第几天？ (判断闰年, 每个月份的天数)
      • D.Subsequence (尺取法)
      • E.Jessica's Reading Problem (尺取法)
    • 二、排序
      • F.稳定排序 (稳定排序的定义)
      • G.[模板]数组排序 (快速排序, 归并排序, std::sort, 堆排序)
      • H.EXCEL排序 (字符串排序, 多关键字排序)
    • 三、贪心
      • I.Saruman's Army (区间贪心)
      • J.Fence Repair (合并果子, 堆排序)
      • K.Cleaning Shifts (最小区间覆盖)
      • L.Protecting the Flowers (推导排序规则)
    • 四、二分
      • M.Dating with girls(1) (二分查找)
      • N.Aggressive cows (二分答案)
      • O.River Hopscotch (二分答案)
      • P.Median

一、暴力

可以参考下面的链接去学习尺取法
1.尺取法详解+例题
E题可能要用到map才能做，可以参考下面的链接学习map
2.map的用法详解

A.水仙花数 (输入到文末)

行末不要输出空格，否则会 P r e s e n t a t i o n Presentation Presentation E r r o r Error Error

//AC code
#include<bits/stdc++.h>  //这是C++的万能头文件, 包含大部分能用到的头文件 
using namespace std;	 //这一句是调用std命名空间定义的标识符, 写上之后, 程序中std::cin、std::cout等就不需要写"std::"这个前缀了 
int n,m;
int main(){while(~scanf("%d%d",&m,&n)){ //输入到文件结尾的方法int flag=0;for(int i=m;i<=n;i++){int t,k=i,sum=0;while(k>0){t=k%10;sum+=t*t*t;k/=10;}if(sum==i){	if(!flag)printf("%d",i);	//处理行末空格 else printf(" %d",i);flag=1;}}if(!flag)printf("no");printf("\n");}
}

B.求数列的和

//AC code
#include<bits/stdc++.h>
using namespace std;
double ans,n;
int m;
int main(){while(~scanf("%lf%d",&n,&m)){ans=0;for(int i=1;i<=m;i++){ans+=n;n=sqrt(n);	//计算立方根的函数}printf("%.2lf\n",ans);}
}

C.第几天？ (判断闰年, 每个月份的天数)

闰年：年份是 4 4 4的倍数但不是 100 100 100的倍数，或者年份是 400 400 400的倍数。

//AC code
#include<bits/stdc++.h>
using namespace std;
int y,m,d,ans;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//每个月的天数
int main(){while(~scanf("%d/%d/%d",&y,&m,&d)){/* 判断闰年,确定二月的天数 */ if(y%400==0||(y%4==0&&y%100!=0))days[2]=29;else days[2]=28;ans=d;for(int i=1;i<m;i++)ans+=days[i];//前m-1个月已经过完了printf("%d\n",ans);}
}

D.Subsequence (尺取法)

先来看第一组样例
N = 10 ， S = 15 N=10，S=15 N=10，S=15
a [ a[ a[ ] ] ]={ 5 , 1 , 3 , 5 , 10 , 7 , 4 , 9 , 2 , 8 5,1,3,5,10,7,4,9,2,8 5,1,3,5,10,7,4,9,2,8}
最简单的方法就是暴力枚举每个数作为起点，每次从这个起点开始往后加，一直加到当前加和 s u m ≥ S sum \geq S sum≥S时停止，更新最小区间长度。

模拟一下就是：
i = 1 时 ， s u m 1 = 5 + [ 1 + 3 + 5 + 10 ] = 24 ≥ S i=1时，sum_1=5+[1+3+5+10]=24 \geq S i=1时，sum1​=5+[1+3+5+10]=24≥S
i = 2 时 ， s u m 2 = [ 1 + 3 + 5 + 10 ] = 19 ≥ S i=2时，sum_2=[1+3+5+10]=19 \geq S i=2时，sum2​=[1+3+5+10]=19≥S
i = 3 时 ， s u m 3 = 3 + 5 + 10 = 18 ≥ S i=3时，sum_3=3+5+10=18 \geq S i=3时，sum3​=3+5+10=18≥S
i = 4 时 ， s u m 4 = 5 + 10 = 15 ≥ S i=4时，sum_4=5+10=15 \geq S i=4时，sum4​=5+10=15≥S
i = 5 时 ， s u m 5 = 10 + 7 = 17 ≥ S i=5时，sum_5=10+7=17 \geq S i=5时，sum5​=10+7=17≥S
…

这样做的时间复杂度是 O ( N 2 ) O(N^2) O(N2)，当 N = 1 0 5 N=10^5 N=105时显然会超时。
容易看出上面当 i = 1 i=1 i=1和 i = 2 i=2 i=2时，[ 1 + 3 + 5 + 10 1+3+5+10 1+3+5+10]这个过程在更换起点后重复进行了一次，如果能避免这样的重复从头累加，应该就能降低时间复杂度。
于是就用到了尺取法/Two Points/双指针法/滑动窗口，这几种叫法都指的是一个东西。
设当前区间的左端点为 L L L，右端点为 R R R，当前区间 [ L , R ] [L, R] [L,R]的加和为 n o w now now，
我们来分析上面暴力枚举的过程：枚举起点，即每次让左端点 L L L++；我们每次都让 n o w now now清零，然后从 R = L R=L R=L开始往后一直加( R R R每次往后移动一个位置)，直到 n o w ≥ S now \geq S now≥S时 R R R停止移动。
i = 1 i=1 i=1时， L = 1 ， R = 5 ， n o w = 24 ≥ S L=1，R=5，now=24 \geq S L=1，R=5，now=24≥S
i = 2 i=2 i=2时， L = 2 ， R = 5 ， n o w = 19 ≥ S L=2，R=5，now=19 \geq S L=2，R=5，now=19≥S
但是试想，如果我们不让 n o w now now每次清零，而是在左端点L往后移动前，我们先让 n o w now now减去 a [ L ] a[L] a[L]，再让 L L L++。如果现在的 n o w < S now<S now<S，只需要从上次的区间右端点 R + 1 R+1 R+1往后继续累加就可以，这样就避免了重复从头累加（类似 [ 1 + 3 + 5 + 10 ] [1+3+5+10] [1+3+5+10]）的这个过程。

更详细一点，我们可以用 w h i l e while while循环来实现这个过程，
①每次我们推进左端点（ L L L++）
②若当前区间加和仍然 ≥ S \geq S ≥S，不需要操作；若当前区间加和 n o w < S now<S now<S，那么我们持续推进右端点（ R R R++），直至 n o w ≥ S now\geq S now≥S右端点停止移动（这个过程也可以用 w h i l e while while实现）。
③判断当前区间加和是否 ≥ S \geq S ≥S，若是，则更新最小区间长度。
▲需要注意的是，在往后移动左右端点时，要附加判断 L 、 R L、R L、R是否越界

这就是尺取法，因为过程中， L L L执行了一次 1 1 1→ N N N， R R R也只执行了一次 1 1 1→ N N N，这是两个比较独立的移动（不是嵌套），所以时间复杂度是 O ( N ) O(N) O(N)。

//AC code
#include<iostream>
using namespace std;
const int N=1e5+7;
int t,n,ans,a[N],s;
int main(){cin>>t;while(t--){scanf("%d%d",&n,&s);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int L=0,R=0,now=0;ans=INT_MAX;//先把最小区间长度设为一个很大的数(INT_MAX是int的上限值)while(L<=n){//越界判断now-=a[L++]; //先让now减去a[L], 再让L++while(now<s&&R<n)now+=a[++R]; //若now<s且不会越界, 就往后推进右端点Rif(now>=s)ans=min(ans,R-L+1); //判断, 更新最小区间长度}if(ans==INT_MAX)printf("0\n");else printf("%d\n",ans);}
}

上面的标程是每次主动推进左端点的，
也可以如下每次主动推进右端点，思路类似，看习惯：

#include<iostream>
using namespace std;
const int N=1e5+7;
int t,n,ans,a[N],s;
int main(){cin>>t;while(t--){scanf("%d%d",&n,&s);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int L=1,R=0,now=0;ans=INT_MAX;while(R<n){now+=a[++R];//右端点右移while(now-a[L]>=s&&L<=R)now-=a[L++];//如果左端点右移后还能满足加和>=S, 就右移if(now>=s)ans=min(ans,R-L+1);}if(ans==INT_MAX)printf("0\n");else printf("%d\n",ans);}
}

E.Jessica’s Reading Problem (尺取法)

思路：先用 m a p map map统计不同页面内容的数量 t o t tot tot。然后设两个指针 L , R L,R L,R，
每次主动右移 R R R并把 a [ R ] a[R] a[R]加入当前区间，此时若 L L L这页内容在区间 [ L + 1 , R ] [L+1, R] [L+1,R]中存在，就一直右移 L L L，这样能保证只有当右移左端点不影响区间不同页面内容数量时才移动。若当前区间内的页面内容数量等于 t o t tot tot，就更新最短区间长度。

//AC code
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e6+7;
int n,a[N],tot,ans=INT_MAX;
map<int,int>mp;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);mp[a[i]]=0;//置为零, 表示当前区间没有包含a[i]这个内容}tot=mp.size();//map的大小就是不同页面内容的数量/* 尺取法 */int L=1,R=0,now=0;while(R<n){now+=(++mp[a[++R]]==1);//右移右端点, 把右端点内容加入进来, 若右端点内容原本不在当前区间中, 就让当前区间内不同的内容数量+1while(mp[a[L]]>1&&L<=R)mp[a[L++]]--;if(now==tot)ans=min(ans,R-L+1);}cout<<ans;
}

二、排序

可以参考下面的链接去学习快速排序、归并排序、std::sort、堆排序
1.快速排序详解
2.归并排序详解
3.std::sort的使用方法（推荐使用这个，高效易写）
*4.堆排序详解（需要用到树的知识，暂时可不要求掌握，但是推荐学会STL中priority_queue优先队列的用法）
5.priority_queue的使用方法（与sort类似，高效易写）

F.稳定排序 (稳定排序的定义)

稳定排序的定义：待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中 R i R_i Ri​领先于 R j R_j Rj​（即 i < j i<j i<j）.若在排序后的序列中 R i R_i Ri​仍然领先于 R j R_j Rj​，则称所用的方法是稳定的。比如 i n t int int数组 [ 1 , 1 , 1 , 6 , 4 ] [1,1,1,6,4] [1,1,1,6,4]中 a [ 0 ] , a [ 1 ] , a [ 2 ] a[0],a[1],a[2] a[0],a[1],a[2]的值相等，在排序时不改变其序列，则称所用的方法是稳定的。 —百度百科

所以这个题，用结构体数组记录数据，并且把输入的第一个数组的下标记录到结构体里。按照成绩为第一关键字降序、下标为第二关键字升序排序。然后依次比对排序完的结构体数组和输入的第二个数组里的姓名和成绩，若成绩姓名都一样，就是正确排序；若成绩都一样，但姓名不同，就是不稳定排序；否则就是错误排序。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=307;
struct node{int id,v;string s;/* 重载小于号＜, 按照第一关键字v降序、第二关键字id升序 */ bool operator <(const node &o)const{return v>o.v||(v==o.v&id<o.id);}
}a[N],b[N];
int n;
int main(){while(cin>>n){for(int i=1;i<=n;i++){cin>>a[i].s>>a[i].v;a[i].id=i;}for(int i=1;i<=n;i++)cin>>b[i].s>>b[i].v;sort(a+1,a+1+n);int flag=1;for(int i=1;i<=n;i++){if(a[i].v!=b[i].v)flag=-1;else if(a[i].s!=b[i].s)flag=0;}if(flag==-1)puts("Error");else if(flag==0)puts("Not Stable");else puts("Right");if(flag!=1){for(int i=1;i<=n;i++)cout<<a[i].s<<" "<<a[i].v<<"\n";}}
}

G.[模板]数组排序 (快速排序, 归并排序, std::sort, 堆排序)

比赛中常用的是std::sort排序和std::priority_queue（优先队列）实现的堆排序。其他的，学习一下归并排序可以用来求逆序对，快速排序和堆排序的代码实现也可以自己了解一下。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,a[N];
int main(){cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);for(int i=1;i<=n;i++)printf("%d ",a[i]);
}

H.EXCEL排序 (字符串排序, 多关键字排序)

按要求的排序规则，写三个std::sort的比较函数cmp就行。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
struct node{string id,name;int grade;
}a[N];
int n,c,cnt;
/* 对应题目中的三种排序规则 */ 
int cmp1(node x,node y){return x.id<y.id;}
int cmp2(node x,node y){return x.name<y.name||(x.name==y.name&&x.id<y.id);}
int cmp3(node x,node y){return x.grade<y.grade||(x.grade==y.grade&&x.id<y.id);}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);/* 这句话用来取消输入输出流同步，可以加快cin、cout的效率但是取消同步流后，就尽量不要在下文使用scanf和printf了 */ while(cin>>n>>c,n!=0){for(int i=1;i<=n;i++)cin>>a[i].id>>a[i].name>>a[i].grade;cout<<"Case "<<++cnt<<":\n";if(c==1)sort(a+1,a+1+n,cmp1);else if(c==2)sort(a+1,a+1+n,cmp2);else sort(a+1,a+1+n,cmp3);for(int i=1;i<=n;i++)cout<<a[i].id<<" "<<a[i].name<<" "<<a[i].grade<<"\n";}
}

三、贪心

可以参考下面的链接去学习贪心算法
1.贪心算法入门详解

I.Saruman’s Army (区间贪心)

思路：因为输入的部队坐标是乱序的，所以先给部队坐标升序排序。
每次贪心选择下一个坐标最小的部队作为左边界，然后寻找能覆盖这个左边界的最远安放palantirs的部队位置，最后寻找上面安放的palantirs能覆盖到的最远右边界。重复进行这样贪心安放一个palantirs的过程，让每个palantirs都覆盖尽可能广的区域，这样的结果就是最小数量。

//AC code
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1007],R,N;
int main(){while(cin>>R>>N){if(R==-1&&N==-1)return 0;for(int i=1;i<=N;i++)scanf("%d",&a[i]);int ans=0,l,r,mid;sort(a+1,a+1+N);l=r=0;while(r<N){l=r+1; //下一个部队作为左端点mid=l;while(a[mid+1]-a[l]<=R&&mid<N)mid++; //寻找能覆盖左边界的最远安放palantirs的位置ans++; //安放在这里r=mid;while(a[r+1]-a[mid]<=R&&r<N)r++; //寻找上面安放的palantirs能覆盖到的最远右边界}cout<<ans<<"\n";}
}

J.Fence Repair (合并果子, 堆排序)

反向思维，把一块长木板切割成 N N N块小木板的过程，想成用 N N N块小木板合并成一块长木坂的过程，即合并果子。
每次贪心取两个最小长度的木板，把它们合并然后放回去，这样切割得到的就是最小花费。
这样贪心的正确性参照哈夫曼树和哈夫曼树最优性的证明
因为 N N N比较大，所以用priority_queue实现每次取两个最小长度的木板，并把它们合并再放回去。priority_queue的单次 p u s h ( ) push() push()、 p o p ( ) pop() pop()操作时间复杂度为 l o g 2 N log_2N log2​N

//AC code
#include<stdio.h> 
#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;//定义简称, 后面可以用LL代替long long使用 
priority_queue<LL,vector<LL>,greater<LL> >q;//定义小根堆(优先队列)
LL ans,n,l;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&l);q.push(l);}for(int i=1;i<n;i++){int k=q.top();q.pop();k+=q.top();q.pop();//从堆里取出两个最小值ans+=k;q.push(k);		   //合并, 把加和放进堆里 }cout<<ans;
}

K.Cleaning Shifts (最小区间覆盖)

思路：是一个最小区间覆盖的经典例题，题目可以化简为在数轴上，给 n n n条线段的左右端点， 选择最少的线段数量，使得这些线段能覆盖区间 [ 1 , t ] [1,t] [1,t]中每一个点。
我们可以先按照第一关键字左端点升序、第二关键字右端点降序排序，
排好序后的第一个线段肯定要选，因为这是能覆盖区间 [ 1 , t ] [1,t] [1,t]左边界，并且右端点最远的线段。所以先判断一下第一个线段的左端点是否能覆盖 1 1 1这个点，如果不能的话就直接输出 − 1 -1 −1；如果能，我们就选定这条线段作为 l i n e 1 line_1 line1​。
然后我们从后面的线段中，找左端点 ≤ l i n e 1 . r i g h t + 1 \leq line_1.right+1 ≤line1​.right+1的线段中(与 l i n e 1 line_1 line1​重叠或者恰好相邻) 右端点最远的线段，然后就可以贪心选择这条线段作为 l i n e 2 line_2 line2​，然后再按照同样的方法，贪心找出所有 l i n e i line_i linei​，就是最少数量。
最后，还要判断一下选择的最后一条线段的右端点是否等于 t t t。

//AC code
#include<stdio.h> 
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3e4+7;
struct node{int l,r;bool operator <(const node &o)const{return l<o.l||(l==o.l&&r>o.r);}
}a[N];
int n,t,ans;
int main(){cin>>n>>t;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+1+n);/* 第一个牛必选, 因为它是能覆盖左边界的牛中右边界最大的 */ if(a[1].l!=1){cout<<-1;return 0;}//第一个牛也无法覆盖左边界 int i=2,ans=1,pre_r=a[1].r,next_r;//pre_r是上一个选用区间的右边界, next_r是下一个要选用的区间能达到的最大右边界 while(i<=n&&pre_r<t){next_r=0;while(a[i].l<=pre_r+1&&i<=n)next_r=max(next_r,a[i++].r);//从有时间重叠或者相邻的区间中找最大右边界 if(next_r>0){//找到的话，就选用这头牛 ans++;pre_r=next_r;}else break; //否则，pre_r+1这个点无法覆盖，结束 } if(pre_r==t)cout<<ans;else cout<<-1;
}

L.Protecting the Flowers (推导排序规则)

假设某个状态有2个牛，分别是 ( d 1 , t 1 ) , ( d 2 , t 2 ) (d_1,t_1),(d_2,t_2) (d1​,t1​),(d2​,t2​)，
我们要决定运输牛 1 1 1和牛 2 2 2的先后顺序，
1.先运输牛 1 1 1，后运输牛 2 2 2的代价为： 2 ∗ t 1 ∗ d 2 2*t_1*d_2 2∗t1​∗d2​
2.先运输牛 2 2 2，后运输牛 1 1 1的代价为： 2 ∗ t 2 ∗ d 1 2*t_2*d_1 2∗t2​∗d1​
如果方案1的代价小于方案2的代价，即 2 ∗ t 1 ∗ d 2 < 2 ∗ t 2 ∗ d 1 2*t_1*d_2<2*t_2*d_1 2∗t1​∗d2​<2∗t2​∗d1​
化简得 t 1 d 1 < t 2 d 2 \frac{t_1}{d_1}<\frac{t_2}{d_2} d1​t1​​<d2​t2​​
所以结论是，当 t 1 d 1 < t 2 d 2 \frac{t_1}{d_1}<\frac{t_2}{d_2} d1​t1​​<d2​t2​​时，先运输牛 1 1 1的代价小。
因此，我们可以按照 t i d i \frac{t_i}{d_i} di​ti​​从小到大排序，贪心优先运输比值小的牛，这样得到的总代价最小。

//AC code
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=1e5+7;
struct node{int t,d;bool operator <(const node &o)const{return (double)t/d<(double)o.t/o.d;}
}a[N];
int n;
long long ans,sum;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&a[i].t,&a[i].d);sum+=a[i].d;}sort(a+1,a+1+n);for(int i=1;i<=n;i++){int k=a[i].t*2;sum-=a[i].d;ans+=k*sum;}cout<<ans;
}

四、二分

可以参考下面的链接去学习二分查找、二分答案算法
1.二分查找详解
2.二分答案详解

M.Dating with girls(1) (二分查找)

思路：我们可以枚举每个数 a [ i ] a[i] a[i]作为 x x x，那么只需要查值在数组中有没有 ( k − x ) (k-x) (k−x)这个数，如果有的话， x + ( k − x ) = = k x+(k-x)==k x+(k−x)==k就是一组解，方程解的数量 + 1 +1 +1。对数组 a [ ] a[ ] a[]排序之后，可以二分查找可以把单次查找的时间复杂度降为 l o g 2 n log_2n log2​n，注意去掉重复的解。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,k,a[N],t,ans;
int main(){cin>>t;while(t--){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n); ans=0;for(int i=1;i<=n;i++){if(i>1&&a[i]==a[i-1])continue;//重复的解只计一次，所以重复的直接跳过 int l=1,r=n,mid;while(l<r){mid=(l+r)/2;if(a[mid]<k-a[i])l=mid+1;else r=mid;}if(a[l]+a[i]==k)ans++;}printf("%d\n",ans);}
}

N.Aggressive cows (二分答案)

思路：一般如果在题目中见到"最大化最小距离",”使最小值最大","the largest minimum distance"等等词，就大概要用二分答案来做。
一般的做法是二分这个最小距离，通过枚举/ d f s dfs dfs等方法判断二分的中间值 m i d mid mid是否可行，根据是否可行，缩小二分的左边界或者右边界，最终把答案区间缩小到一个具体值。

所以这个题，我们就二分这个最小距离， c h e c k ( check( check(二分中间值 m i d ) mid) mid)的方法是，枚举每一个牛棚，若当前牛棚 x [ i ] x[i] x[i]和上一个牛棚 x [ p r e ] x[pre] x[pre]的距离 ≥ m i d \geq mid ≥mid，就选择上 i i i这个牛棚，否则就不选这一个牛棚，然后继续找下一个。
枚举完后，若选择的牛棚数量 ≥ c \geq c ≥c(牛的数量)，就说明这个中间值是一个可行的最小距离方案，可以继续增大最小距离；否则，就说明不可行，需要缩小最小距离，使得能找出至少 c c c个牛棚。

写二分 w h i l e while while循环结束条件，和 c h e c k check check检验完后要缩小哪个边界时，要结合具体情况分析，可以假设当前区间 [ L , R ] [L,R] [L,R]中只剩下 L L L和 R R R三个点或者两个点入手分析。

//AC code
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n,x[N],c;
int check(int mid){int cnt=1,pre=1;//贪心找最小距离为mid之下的最大可用牛棚数量，第一个牛棚必选 for(int i=2;i<=n;i++){if(x[i]-x[pre]>=mid){cnt++;pre=i;}//else continue;}return (cnt>=c);//如果cnt>=c就说明mid这个最小距离可行，返回1 
}
int main(){cin>>n>>c;for(int i=1;i<=n;i++)scanf("%d",&x[i]);sort(x+1,x+1+n);int l=1,r=1e9,mid;while(l<r){mid=(l+r+1)/2;if(check(mid))l=mid;//方案可行，就继续扩大最小值 else r=mid-1;}cout<<l;
}

O.River Hopscotch (二分答案)

思路：二分这个最短距离。检验中间值的方法与上个题类似，如果枚举的当前石头与上个未移除的石头之间的距离小于二分出来的最短距离，就移除当前石头，否则就继续找下一块石头。
枚举完后，判断移除的石头数量，如果需要移除的石头 ≥ m \geq m ≥m(最多移除的石头数量)，就需要缩小右边界，找更小的最短距离使得移除较少的石头。否则，当前方案可行，可以继续右移左边界，尝试找更大的最短距离。

//AC code
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=5e4+7;
int n,m,L,d[N];
int check(int mid){int cnt=0,pre=0;for(int i=1;i<=n+1;i++){if(d[i]-d[pre]<mid)cnt++;else pre=i;}if(cnt<=m)return 1;return 0;
}
int main(){cin>>L>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&d[i]);sort(d+1,d+1+n);d[0]=0; d[n+1]=L;int l=1,r=L,mid;while(l<r){//二分最短跳跃距离 mid=(l+r+1)/2;if(check(mid))l=mid;else r=mid-1;}cout<<l;
}

P.Median

思路：这个题做法比较巧妙，设 f [ t ] f[t] f[t]为所有可重复差值中， ∣ X i − X j ≤ t ∣ |X_i-X_j\leq t| ∣Xi​−Xj​≤t∣的差值数量，那么这个函数应该具有单调性。
所以我们可以二分这个最大差值 t t t，检验二分中间值 m i d mid mid时，找出满足 ∣ X i − X j ≤ m i d ∣ |X_i-X_j\leq mid| ∣Xi​−Xj​≤mid∣的差值数量，如果这个数量 ≥ \geq ≥总差值数量 / 2 /2 /2，那么我们要找的差值中位数，应该比当前二分的最大差值要小，所以要缩小右边界；否则，缩小左边界。边界最终会缩小到只剩一个具体的数，就恰好是要找的差值中位数。
其中，找出满足 ∣ X i − X j ≤ m i d ∣ |X_i-X_j\leq mid| ∣Xi​−Xj​≤mid∣的差值数量的方法是：
给 X X X数组从小到大排序，枚举每一个数 X i X_i Xi​作为 X i X_i Xi​和 X j X_j Xj​中较大的那个数，那么 X j X_j Xj​应该从 1 ≤ j < i 1\leq j<i 1≤j<i中取，绝对值符号此时可以去掉，移项变成
X j ≥ X i − m i d , ( 1 ≤ j < i ) X_j\geq X_i-mid, (1\leq j<i) Xj​≥Xi​−mid,(1≤j<i)
也就是我们要找满足 X j ≥ X i − m i d , ( 1 ≤ j < i ) X_j\geq X_i-mid, (1\leq j<i) Xj​≥Xi​−mid,(1≤j<i)的 j j j的数量，所以可以二分从 X X X数组中找 1 1 1到 i i i中，第一个大于或等于 X i − m i d X_i-mid Xi​−mid的数的位置，从这个位置到位置 i − 1 i-1 i−1的所有数都应该满足上式，累加枚举每个数找到的满足上式的数量，就是满足 ∣ X i − X j ≤ m i d ∣ |X_i-X_j\leq mid| ∣Xi​−Xj​≤mid∣的所有差值数量。
这个简单二分的过程，可以用 l o w e r _ b o u n d lower\_bound lower_bound函数来实现。
参考 l o w e r _ b o u n d lower\_bound lower_bound的基本用法

//AC code
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n,x[N];
int check(int mid,int k){/* 判断最大差值为mid时, 是否存在k个差值 */ int cnt=0;for(int i=1;i<=n;i++){int p=lower_bound(x+1,x+i,x[i]-mid)-x;//找x[1]到x[i-1]中,>=x[i]-mid的第一个数的位置cnt+=i-p;}if(cnt>=k)return 0;return 1;
}
int main(){while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%d",&x[i]);sort(x+1,x+1+n);int k=(n*(n-1)/2+1)/2;int l=1,r=x[n],mid;while(l<r){//二分最大差值 mid=(l+r)/2;if(check(mid,k))l=mid+1;else r=mid;}printf("%d\n",l);}
}

QLU

欢迎大家来做QLU_ACM寒假组织的专题训练🎈
本周专题关于 暴力、排序、贪心、二分

比赛链接 [密码2021]

专题目录

    • 一、暴力
      • A.水仙花数 (输入到文末)
      • B.求数列的和
      • C.第几天？ (判断闰年, 每个月份的天数)
      • D.Subsequence (尺取法)
      • E.Jessica's Reading Problem (尺取法)
    • 二、排序
      • F.稳定排序 (稳定排序的定义)
      • G.[模板]数组排序 (快速排序, 归并排序, std::sort, 堆排序)
      • H.EXCEL排序 (字符串排序, 多关键字排序)
    • 三、贪心
      • I.Saruman's Army (区间贪心)
      • J.Fence Repair (合并果子, 堆排序)
      • K.Cleaning Shifts (最小区间覆盖)
      • L.Protecting the Flowers (推导排序规则)
    • 四、二分
      • M.Dating with girls(1) (二分查找)
      • N.Aggressive cows (二分答案)
      • O.River Hopscotch (二分答案)
      • P.Median

一、暴力

可以参考下面的链接去学习尺取法
1.尺取法详解+例题
E题可能要用到map才能做，可以参考下面的链接学习map
2.map的用法详解

A.水仙花数 (输入到文末)

行末不要输出空格，否则会 P r e s e n t a t i o n Presentation Presentation E r r o r Error Error

//AC code
#include<bits/stdc++.h>  //这是C++的万能头文件, 包含大部分能用到的头文件 
using namespace std;	 //这一句是调用std命名空间定义的标识符, 写上之后, 程序中std::cin、std::cout等就不需要写"std::"这个前缀了 
int n,m;
int main(){while(~scanf("%d%d",&m,&n)){ //输入到文件结尾的方法int flag=0;for(int i=m;i<=n;i++){int t,k=i,sum=0;while(k>0){t=k%10;sum+=t*t*t;k/=10;}if(sum==i){	if(!flag)printf("%d",i);	//处理行末空格 else printf(" %d",i);flag=1;}}if(!flag)printf("no");printf("\n");}
}

B.求数列的和

//AC code
#include<bits/stdc++.h>
using namespace std;
double ans,n;
int m;
int main(){while(~scanf("%lf%d",&n,&m)){ans=0;for(int i=1;i<=m;i++){ans+=n;n=sqrt(n);	//计算立方根的函数}printf("%.2lf\n",ans);}
}

C.第几天？ (判断闰年, 每个月份的天数)

闰年：年份是 4 4 4的倍数但不是 100 100 100的倍数，或者年份是 400 400 400的倍数。

//AC code
#include<bits/stdc++.h>
using namespace std;
int y,m,d,ans;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//每个月的天数
int main(){while(~scanf("%d/%d/%d",&y,&m,&d)){/* 判断闰年,确定二月的天数 */ if(y%400==0||(y%4==0&&y%100!=0))days[2]=29;else days[2]=28;ans=d;for(int i=1;i<m;i++)ans+=days[i];//前m-1个月已经过完了printf("%d\n",ans);}
}

D.Subsequence (尺取法)

先来看第一组样例
N = 10 ， S = 15 N=10，S=15 N=10，S=15
a [ a[ a[ ] ] ]={ 5 , 1 , 3 , 5 , 10 , 7 , 4 , 9 , 2 , 8 5,1,3,5,10,7,4,9,2,8 5,1,3,5,10,7,4,9,2,8}
最简单的方法就是暴力枚举每个数作为起点，每次从这个起点开始往后加，一直加到当前加和 s u m ≥ S sum \geq S sum≥S时停止，更新最小区间长度。

模拟一下就是：
i = 1 时 ， s u m 1 = 5 + [ 1 + 3 + 5 + 10 ] = 24 ≥ S i=1时，sum_1=5+[1+3+5+10]=24 \geq S i=1时，sum1​=5+[1+3+5+10]=24≥S
i = 2 时 ， s u m 2 = [ 1 + 3 + 5 + 10 ] = 19 ≥ S i=2时，sum_2=[1+3+5+10]=19 \geq S i=2时，sum2​=[1+3+5+10]=19≥S
i = 3 时 ， s u m 3 = 3 + 5 + 10 = 18 ≥ S i=3时，sum_3=3+5+10=18 \geq S i=3时，sum3​=3+5+10=18≥S
i = 4 时 ， s u m 4 = 5 + 10 = 15 ≥ S i=4时，sum_4=5+10=15 \geq S i=4时，sum4​=5+10=15≥S
i = 5 时 ， s u m 5 = 10 + 7 = 17 ≥ S i=5时，sum_5=10+7=17 \geq S i=5时，sum5​=10+7=17≥S
…

这样做的时间复杂度是 O ( N 2 ) O(N^2) O(N2)，当 N = 1 0 5 N=10^5 N=105时显然会超时。
容易看出上面当 i = 1 i=1 i=1和 i = 2 i=2 i=2时，[ 1 + 3 + 5 + 10 1+3+5+10 1+3+5+10]这个过程在更换起点后重复进行了一次，如果能避免这样的重复从头累加，应该就能降低时间复杂度。
于是就用到了尺取法/Two Points/双指针法/滑动窗口，这几种叫法都指的是一个东西。
设当前区间的左端点为 L L L，右端点为 R R R，当前区间 [ L , R ] [L, R] [L,R]的加和为 n o w now now，
我们来分析上面暴力枚举的过程：枚举起点，即每次让左端点 L L L++；我们每次都让 n o w now now清零，然后从 R = L R=L R=L开始往后一直加( R R R每次往后移动一个位置)，直到 n o w ≥ S now \geq S now≥S时 R R R停止移动。
i = 1 i=1 i=1时， L = 1 ， R = 5 ， n o w = 24 ≥ S L=1，R=5，now=24 \geq S L=1，R=5，now=24≥S
i = 2 i=2 i=2时， L = 2 ， R = 5 ， n o w = 19 ≥ S L=2，R=5，now=19 \geq S L=2，R=5，now=19≥S
但是试想，如果我们不让 n o w now now每次清零，而是在左端点L往后移动前，我们先让 n o w now now减去 a [ L ] a[L] a[L]，再让 L L L++。如果现在的 n o w < S now<S now<S，只需要从上次的区间右端点 R + 1 R+1 R+1往后继续累加就可以，这样就避免了重复从头累加（类似 [ 1 + 3 + 5 + 10 ] [1+3+5+10] [1+3+5+10]）的这个过程。

更详细一点，我们可以用 w h i l e while while循环来实现这个过程，
①每次我们推进左端点（ L L L++）
②若当前区间加和仍然 ≥ S \geq S ≥S，不需要操作；若当前区间加和 n o w < S now<S now<S，那么我们持续推进右端点（ R R R++），直至 n o w ≥ S now\geq S now≥S右端点停止移动（这个过程也可以用 w h i l e while while实现）。
③判断当前区间加和是否 ≥ S \geq S ≥S，若是，则更新最小区间长度。
▲需要注意的是，在往后移动左右端点时，要附加判断 L 、 R L、R L、R是否越界

这就是尺取法，因为过程中， L L L执行了一次 1 1 1→ N N N， R R R也只执行了一次 1 1 1→ N N N，这是两个比较独立的移动（不是嵌套），所以时间复杂度是 O ( N ) O(N) O(N)。

//AC code
#include<iostream>
using namespace std;
const int N=1e5+7;
int t,n,ans,a[N],s;
int main(){cin>>t;while(t--){scanf("%d%d",&n,&s);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int L=0,R=0,now=0;ans=INT_MAX;//先把最小区间长度设为一个很大的数(INT_MAX是int的上限值)while(L<=n){//越界判断now-=a[L++]; //先让now减去a[L], 再让L++while(now<s&&R<n)now+=a[++R]; //若now<s且不会越界, 就往后推进右端点Rif(now>=s)ans=min(ans,R-L+1); //判断, 更新最小区间长度}if(ans==INT_MAX)printf("0\n");else printf("%d\n",ans);}
}

上面的标程是每次主动推进左端点的，
也可以如下每次主动推进右端点，思路类似，看习惯：

#include<iostream>
using namespace std;
const int N=1e5+7;
int t,n,ans,a[N],s;
int main(){cin>>t;while(t--){scanf("%d%d",&n,&s);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int L=1,R=0,now=0;ans=INT_MAX;while(R<n){now+=a[++R];//右端点右移while(now-a[L]>=s&&L<=R)now-=a[L++];//如果左端点右移后还能满足加和>=S, 就右移if(now>=s)ans=min(ans,R-L+1);}if(ans==INT_MAX)printf("0\n");else printf("%d\n",ans);}
}

E.Jessica’s Reading Problem (尺取法)

思路：先用 m a p map map统计不同页面内容的数量 t o t tot tot。然后设两个指针 L , R L,R L,R，
每次主动右移 R R R并把 a [ R ] a[R] a[R]加入当前区间，此时若 L L L这页内容在区间 [ L + 1 , R ] [L+1, R] [L+1,R]中存在，就一直右移 L L L，这样能保证只有当右移左端点不影响区间不同页面内容数量时才移动。若当前区间内的页面内容数量等于 t o t tot tot，就更新最短区间长度。

//AC code
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e6+7;
int n,a[N],tot,ans=INT_MAX;
map<int,int>mp;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);mp[a[i]]=0;//置为零, 表示当前区间没有包含a[i]这个内容}tot=mp.size();//map的大小就是不同页面内容的数量/* 尺取法 */int L=1,R=0,now=0;while(R<n){now+=(++mp[a[++R]]==1);//右移右端点, 把右端点内容加入进来, 若右端点内容原本不在当前区间中, 就让当前区间内不同的内容数量+1while(mp[a[L]]>1&&L<=R)mp[a[L++]]--;if(now==tot)ans=min(ans,R-L+1);}cout<<ans;
}

二、排序

可以参考下面的链接去学习快速排序、归并排序、std::sort、堆排序
1.快速排序详解
2.归并排序详解
3.std::sort的使用方法（推荐使用这个，高效易写）
*4.堆排序详解（需要用到树的知识，暂时可不要求掌握，但是推荐学会STL中priority_queue优先队列的用法）
5.priority_queue的使用方法（与sort类似，高效易写）

F.稳定排序 (稳定排序的定义)

稳定排序的定义：待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中 R i R_i Ri​领先于 R j R_j Rj​（即 i < j i<j i<j）.若在排序后的序列中 R i R_i Ri​仍然领先于 R j R_j Rj​，则称所用的方法是稳定的。比如 i n t int int数组 [ 1 , 1 , 1 , 6 , 4 ] [1,1,1,6,4] [1,1,1,6,4]中 a [ 0 ] , a [ 1 ] , a [ 2 ] a[0],a[1],a[2] a[0],a[1],a[2]的值相等，在排序时不改变其序列，则称所用的方法是稳定的。 —百度百科

所以这个题，用结构体数组记录数据，并且把输入的第一个数组的下标记录到结构体里。按照成绩为第一关键字降序、下标为第二关键字升序排序。然后依次比对排序完的结构体数组和输入的第二个数组里的姓名和成绩，若成绩姓名都一样，就是正确排序；若成绩都一样，但姓名不同，就是不稳定排序；否则就是错误排序。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=307;
struct node{int id,v;string s;/* 重载小于号＜, 按照第一关键字v降序、第二关键字id升序 */ bool operator <(const node &o)const{return v>o.v||(v==o.v&id<o.id);}
}a[N],b[N];
int n;
int main(){while(cin>>n){for(int i=1;i<=n;i++){cin>>a[i].s>>a[i].v;a[i].id=i;}for(int i=1;i<=n;i++)cin>>b[i].s>>b[i].v;sort(a+1,a+1+n);int flag=1;for(int i=1;i<=n;i++){if(a[i].v!=b[i].v)flag=-1;else if(a[i].s!=b[i].s)flag=0;}if(flag==-1)puts("Error");else if(flag==0)puts("Not Stable");else puts("Right");if(flag!=1){for(int i=1;i<=n;i++)cout<<a[i].s<<" "<<a[i].v<<"\n";}}
}

G.[模板]数组排序 (快速排序, 归并排序, std::sort, 堆排序)

比赛中常用的是std::sort排序和std::priority_queue（优先队列）实现的堆排序。其他的，学习一下归并排序可以用来求逆序对，快速排序和堆排序的代码实现也可以自己了解一下。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,a[N];
int main(){cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);for(int i=1;i<=n;i++)printf("%d ",a[i]);
}

H.EXCEL排序 (字符串排序, 多关键字排序)

按要求的排序规则，写三个std::sort的比较函数cmp就行。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
struct node{string id,name;int grade;
}a[N];
int n,c,cnt;
/* 对应题目中的三种排序规则 */ 
int cmp1(node x,node y){return x.id<y.id;}
int cmp2(node x,node y){return x.name<y.name||(x.name==y.name&&x.id<y.id);}
int cmp3(node x,node y){return x.grade<y.grade||(x.grade==y.grade&&x.id<y.id);}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);/* 这句话用来取消输入输出流同步，可以加快cin、cout的效率但是取消同步流后，就尽量不要在下文使用scanf和printf了 */ while(cin>>n>>c,n!=0){for(int i=1;i<=n;i++)cin>>a[i].id>>a[i].name>>a[i].grade;cout<<"Case "<<++cnt<<":\n";if(c==1)sort(a+1,a+1+n,cmp1);else if(c==2)sort(a+1,a+1+n,cmp2);else sort(a+1,a+1+n,cmp3);for(int i=1;i<=n;i++)cout<<a[i].id<<" "<<a[i].name<<" "<<a[i].grade<<"\n";}
}

三、贪心

可以参考下面的链接去学习贪心算法
1.贪心算法入门详解

I.Saruman’s Army (区间贪心)

思路：因为输入的部队坐标是乱序的，所以先给部队坐标升序排序。
每次贪心选择下一个坐标最小的部队作为左边界，然后寻找能覆盖这个左边界的最远安放palantirs的部队位置，最后寻找上面安放的palantirs能覆盖到的最远右边界。重复进行这样贪心安放一个palantirs的过程，让每个palantirs都覆盖尽可能广的区域，这样的结果就是最小数量。

//AC code
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1007],R,N;
int main(){while(cin>>R>>N){if(R==-1&&N==-1)return 0;for(int i=1;i<=N;i++)scanf("%d",&a[i]);int ans=0,l,r,mid;sort(a+1,a+1+N);l=r=0;while(r<N){l=r+1; //下一个部队作为左端点mid=l;while(a[mid+1]-a[l]<=R&&mid<N)mid++; //寻找能覆盖左边界的最远安放palantirs的位置ans++; //安放在这里r=mid;while(a[r+1]-a[mid]<=R&&r<N)r++; //寻找上面安放的palantirs能覆盖到的最远右边界}cout<<ans<<"\n";}
}

J.Fence Repair (合并果子, 堆排序)

反向思维，把一块长木板切割成 N N N块小木板的过程，想成用 N N N块小木板合并成一块长木坂的过程，即合并果子。
每次贪心取两个最小长度的木板，把它们合并然后放回去，这样切割得到的就是最小花费。
这样贪心的正确性参照哈夫曼树和哈夫曼树最优性的证明
因为 N N N比较大，所以用priority_queue实现每次取两个最小长度的木板，并把它们合并再放回去。priority_queue的单次 p u s h ( ) push() push()、 p o p ( ) pop() pop()操作时间复杂度为 l o g 2 N log_2N log2​N

//AC code
#include<stdio.h> 
#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;//定义简称, 后面可以用LL代替long long使用 
priority_queue<LL,vector<LL>,greater<LL> >q;//定义小根堆(优先队列)
LL ans,n,l;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&l);q.push(l);}for(int i=1;i<n;i++){int k=q.top();q.pop();k+=q.top();q.pop();//从堆里取出两个最小值ans+=k;q.push(k);		   //合并, 把加和放进堆里 }cout<<ans;
}

K.Cleaning Shifts (最小区间覆盖)

思路：是一个最小区间覆盖的经典例题，题目可以化简为在数轴上，给 n n n条线段的左右端点， 选择最少的线段数量，使得这些线段能覆盖区间 [ 1 , t ] [1,t] [1,t]中每一个点。
我们可以先按照第一关键字左端点升序、第二关键字右端点降序排序，
排好序后的第一个线段肯定要选，因为这是能覆盖区间 [ 1 , t ] [1,t] [1,t]左边界，并且右端点最远的线段。所以先判断一下第一个线段的左端点是否能覆盖 1 1 1这个点，如果不能的话就直接输出 − 1 -1 −1；如果能，我们就选定这条线段作为 l i n e 1 line_1 line1​。
然后我们从后面的线段中，找左端点 ≤ l i n e 1 . r i g h t + 1 \leq line_1.right+1 ≤line1​.right+1的线段中(与 l i n e 1 line_1 line1​重叠或者恰好相邻) 右端点最远的线段，然后就可以贪心选择这条线段作为 l i n e 2 line_2 line2​，然后再按照同样的方法，贪心找出所有 l i n e i line_i linei​，就是最少数量。
最后，还要判断一下选择的最后一条线段的右端点是否等于 t t t。

//AC code
#include<stdio.h> 
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3e4+7;
struct node{int l,r;bool operator <(const node &o)const{return l<o.l||(l==o.l&&r>o.r);}
}a[N];
int n,t,ans;
int main(){cin>>n>>t;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+1+n);/* 第一个牛必选, 因为它是能覆盖左边界的牛中右边界最大的 */ if(a[1].l!=1){cout<<-1;return 0;}//第一个牛也无法覆盖左边界 int i=2,ans=1,pre_r=a[1].r,next_r;//pre_r是上一个选用区间的右边界, next_r是下一个要选用的区间能达到的最大右边界 while(i<=n&&pre_r<t){next_r=0;while(a[i].l<=pre_r+1&&i<=n)next_r=max(next_r,a[i++].r);//从有时间重叠或者相邻的区间中找最大右边界 if(next_r>0){//找到的话，就选用这头牛 ans++;pre_r=next_r;}else break; //否则，pre_r+1这个点无法覆盖，结束 } if(pre_r==t)cout<<ans;else cout<<-1;
}

L.Protecting the Flowers (推导排序规则)

假设某个状态有2个牛，分别是 ( d 1 , t 1 ) , ( d 2 , t 2 ) (d_1,t_1),(d_2,t_2) (d1​,t1​),(d2​,t2​)，
我们要决定运输牛 1 1 1和牛 2 2 2的先后顺序，
1.先运输牛 1 1 1，后运输牛 2 2 2的代价为： 2 ∗ t 1 ∗ d 2 2*t_1*d_2 2∗t1​∗d2​
2.先运输牛 2 2 2，后运输牛 1 1 1的代价为： 2 ∗ t 2 ∗ d 1 2*t_2*d_1 2∗t2​∗d1​
如果方案1的代价小于方案2的代价，即 2 ∗ t 1 ∗ d 2 < 2 ∗ t 2 ∗ d 1 2*t_1*d_2<2*t_2*d_1 2∗t1​∗d2​<2∗t2​∗d1​
化简得 t 1 d 1 < t 2 d 2 \frac{t_1}{d_1}<\frac{t_2}{d_2} d1​t1​​<d2​t2​​
所以结论是，当 t 1 d 1 < t 2 d 2 \frac{t_1}{d_1}<\frac{t_2}{d_2} d1​t1​​<d2​t2​​时，先运输牛 1 1 1的代价小。
因此，我们可以按照 t i d i \frac{t_i}{d_i} di​ti​​从小到大排序，贪心优先运输比值小的牛，这样得到的总代价最小。

//AC code
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=1e5+7;
struct node{int t,d;bool operator <(const node &o)const{return (double)t/d<(double)o.t/o.d;}
}a[N];
int n;
long long ans,sum;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&a[i].t,&a[i].d);sum+=a[i].d;}sort(a+1,a+1+n);for(int i=1;i<=n;i++){int k=a[i].t*2;sum-=a[i].d;ans+=k*sum;}cout<<ans;
}

四、二分

可以参考下面的链接去学习二分查找、二分答案算法
1.二分查找详解
2.二分答案详解

M.Dating with girls(1) (二分查找)

思路：我们可以枚举每个数 a [ i ] a[i] a[i]作为 x x x，那么只需要查值在数组中有没有 ( k − x ) (k-x) (k−x)这个数，如果有的话， x + ( k − x ) = = k x+(k-x)==k x+(k−x)==k就是一组解，方程解的数量 + 1 +1 +1。对数组 a [ ] a[ ] a[]排序之后，可以二分查找可以把单次查找的时间复杂度降为 l o g 2 n log_2n log2​n，注意去掉重复的解。

//AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,k,a[N],t,ans;
int main(){cin>>t;while(t--){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n); ans=0;for(int i=1;i<=n;i++){if(i>1&&a[i]==a[i-1])continue;//重复的解只计一次，所以重复的直接跳过 int l=1,r=n,mid;while(l<r){mid=(l+r)/2;if(a[mid]<k-a[i])l=mid+1;else r=mid;}if(a[l]+a[i]==k)ans++;}printf("%d\n",ans);}
}

N.Aggressive cows (二分答案)

思路：一般如果在题目中见到"最大化最小距离",”使最小值最大","the largest minimum distance"等等词，就大概要用二分答案来做。
一般的做法是二分这个最小距离，通过枚举/ d f s dfs dfs等方法判断二分的中间值 m i d mid mid是否可行，根据是否可行，缩小二分的左边界或者右边界，最终把答案区间缩小到一个具体值。

所以这个题，我们就二分这个最小距离， c h e c k ( check( check(二分中间值 m i d ) mid) mid)的方法是，枚举每一个牛棚，若当前牛棚 x [ i ] x[i] x[i]和上一个牛棚 x [ p r e ] x[pre] x[pre]的距离 ≥ m i d \geq mid ≥mid，就选择上 i i i这个牛棚，否则就不选这一个牛棚，然后继续找下一个。
枚举完后，若选择的牛棚数量 ≥ c \geq c ≥c(牛的数量)，就说明这个中间值是一个可行的最小距离方案，可以继续增大最小距离；否则，就说明不可行，需要缩小最小距离，使得能找出至少 c c c个牛棚。

写二分 w h i l e while while循环结束条件，和 c h e c k check check检验完后要缩小哪个边界时，要结合具体情况分析，可以假设当前区间 [ L , R ] [L,R] [L,R]中只剩下 L L L和 R R R三个点或者两个点入手分析。

//AC code
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n,x[N],c;
int check(int mid){int cnt=1,pre=1;//贪心找最小距离为mid之下的最大可用牛棚数量，第一个牛棚必选 for(int i=2;i<=n;i++){if(x[i]-x[pre]>=mid){cnt++;pre=i;}//else continue;}return (cnt>=c);//如果cnt>=c就说明mid这个最小距离可行，返回1 
}
int main(){cin>>n>>c;for(int i=1;i<=n;i++)scanf("%d",&x[i]);sort(x+1,x+1+n);int l=1,r=1e9,mid;while(l<r){mid=(l+r+1)/2;if(check(mid))l=mid;//方案可行，就继续扩大最小值 else r=mid-1;}cout<<l;
}

O.River Hopscotch (二分答案)

思路：二分这个最短距离。检验中间值的方法与上个题类似，如果枚举的当前石头与上个未移除的石头之间的距离小于二分出来的最短距离，就移除当前石头，否则就继续找下一块石头。
枚举完后，判断移除的石头数量，如果需要移除的石头 ≥ m \geq m ≥m(最多移除的石头数量)，就需要缩小右边界，找更小的最短距离使得移除较少的石头。否则，当前方案可行，可以继续右移左边界，尝试找更大的最短距离。

//AC code
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=5e4+7;
int n,m,L,d[N];
int check(int mid){int cnt=0,pre=0;for(int i=1;i<=n+1;i++){if(d[i]-d[pre]<mid)cnt++;else pre=i;}if(cnt<=m)return 1;return 0;
}
int main(){cin>>L>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&d[i]);sort(d+1,d+1+n);d[0]=0; d[n+1]=L;int l=1,r=L,mid;while(l<r){//二分最短跳跃距离 mid=(l+r+1)/2;if(check(mid))l=mid;else r=mid-1;}cout<<l;
}

P.Median

思路：这个题做法比较巧妙，设 f [ t ] f[t] f[t]为所有可重复差值中， ∣ X i − X j ≤ t ∣ |X_i-X_j\leq t| ∣Xi​−Xj​≤t∣的差值数量，那么这个函数应该具有单调性。
所以我们可以二分这个最大差值 t t t，检验二分中间值 m i d mid mid时，找出满足 ∣ X i − X j ≤ m i d ∣ |X_i-X_j\leq mid| ∣Xi​−Xj​≤mid∣的差值数量，如果这个数量 ≥ \geq ≥总差值数量 / 2 /2 /2，那么我们要找的差值中位数，应该比当前二分的最大差值要小，所以要缩小右边界；否则，缩小左边界。边界最终会缩小到只剩一个具体的数，就恰好是要找的差值中位数。
其中，找出满足 ∣ X i − X j ≤ m i d ∣ |X_i-X_j\leq mid| ∣Xi​−Xj​≤mid∣的差值数量的方法是：
给 X X X数组从小到大排序，枚举每一个数 X i X_i Xi​作为 X i X_i Xi​和 X j X_j Xj​中较大的那个数，那么 X j X_j Xj​应该从 1 ≤ j < i 1\leq j<i 1≤j<i中取，绝对值符号此时可以去掉，移项变成
X j ≥ X i − m i d , ( 1 ≤ j < i ) X_j\geq X_i-mid, (1\leq j<i) Xj​≥Xi​−mid,(1≤j<i)
也就是我们要找满足 X j ≥ X i − m i d , ( 1 ≤ j < i ) X_j\geq X_i-mid, (1\leq j<i) Xj​≥Xi​−mid,(1≤j<i)的 j j j的数量，所以可以二分从 X X X数组中找 1 1 1到 i i i中，第一个大于或等于 X i − m i d X_i-mid Xi​−mid的数的位置，从这个位置到位置 i − 1 i-1 i−1的所有数都应该满足上式，累加枚举每个数找到的满足上式的数量，就是满足 ∣ X i − X j ≤ m i d ∣ |X_i-X_j\leq mid| ∣Xi​−Xj​≤mid∣的所有差值数量。
这个简单二分的过程，可以用 l o w e r _ b o u n d lower\_bound lower_bound函数来实现。
参考 l o w e r _ b o u n d lower\_bound lower_bound的基本用法

//AC code
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n,x[N];
int check(int mid,int k){/* 判断最大差值为mid时, 是否存在k个差值 */ int cnt=0;for(int i=1;i<=n;i++){int p=lower_bound(x+1,x+i,x[i]-mid)-x;//找x[1]到x[i-1]中,>=x[i]-mid的第一个数的位置cnt+=i-p;}if(cnt>=k)return 0;return 1;
}
int main(){while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%d",&x[i]);sort(x+1,x+1+n);int k=(n*(n-1)/2+1)/2;int l=1,r=x[n],mid;while(l<r){//二分最大差值 mid=(l+r)/2;if(check(mid,k))l=mid+1;else r=mid;}printf("%d\n",l);}
}

本文标签： QLU

版权声明：本文标题：QLU 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://it.en369.cn/IT/1687645863a124459.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。