可反悔的贪心。从小到大对倒塌时长排序，先修快倒塌的（从小到大枚举修理时长）。如果时间不够修当前的楼，就先判断这个楼是否有必要修（修它的用时<修之前楼用时的最大值，就有必要修）。如果没必要就不修，如果有必要就把前面修的时间最长的楼去掉，不去修它。 #include <bits/stdc++.h> using namespace std; typedef long long ll; priority_queue<ll> q;//大根堆 struct build{ ll t1; ll t2; }a[150010]; ll n; int comp(struct build...

按照s从大到小排序。先选s大、宽容的人，他能接受的人最多，然后再不断选s小的人。如果人数超了，就把战斗力最低的人踢掉（贪心完的后悔）。这样其实是决定枚举最大人数的人，先找s大的人，就不会对后面有影响，不会出现：我的s满足了，但上一个选进来的人s不满足。这样保证后面来的人能容忍的人少，前面人的s大，不影响结果。保证人数的确定，由后来的人决定和影响，这样每个人才能有决定队伍人数的机会。这样也是在从大到小枚举队伍中的人数，每次看看符合s的人有多少，再从中挑v大的人 #include <bits/stdc++.h> using namespace std; typedef long lon...

利用对顶堆求中位数 我们可以构造两个堆，堆1放小的数，堆2放大的数。堆1为大顶堆，记录这些小的数中的最大者；堆2为小顶堆，记录这些大的数中的最小者。 每次输入一个数，只需要把它和小顶堆的最大数比较，若这个数小于堆顶，表明这个数小，就放进小顶堆；若这个数大于堆顶，表明这个数大，放进大顶堆。 当输入的元素个数为偶，两个堆可能元素个数相等，也可能相差2.若相差2，就把堆顶挪到另一个堆中，使得两个堆的元素个数一致；当输入的元素个数为奇，由于输入之前两堆的元素个数相等，因此现在两个堆的元素个数相差1，所以只要找到元素个数多的堆，输出堆顶，就是所求中位数。 题目已经保证都是32位整数，且没有加减乘除操作，...

典型哈夫曼树问题方法一：使用小根堆解决 #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; priority_queue<int,vector<int>,greater<int>> q; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n ; for(int i=0;i<n;i++){ int x; cin >> x; q.pu...

用数组du作为单调队列，把对应a中的下标记录下来。l和r分别是数组du的左右界。以求区间最大为例，如果后来的元素更大，则前面比它小的元素就没机会成为最大了，直接去掉。若后来的元素更小，由于位序偏后，可能会成为某个区间的最大。当区间里的数多于k个，就把最前面的元素去掉。最终du对应a中的元素单调下降，最前面的元素a[du[l]]就是最大。 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,k; ll a[1000010]; int du[1000010];//记录区间的第i个数在a中的下标...

用数组du作为单调队列，把对应a中的下标记录下来。l和r分别是数组du的左右界。以求区间最大为例，如果后来的元素更大，则前面比它小的元素就没机会成为最大了，直接去掉。若后来的元素更小，由于位序偏后，可能会成为某个区间的最大。当区间里的数多于k个，就把最前面的元素去掉。最终du对应a中的元素单调下降，最前面的元素a[du[l]]就是最大。 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,k; ll a[1000010]; int du[1000010];//记录区间的第i个数在a中的下标...

如果x1>x2，那么floor(px1)>floor(px2)，且x1-floor(px1)>x2-floor(px2)因此，可以把原来的蚯蚓、切开后长的蚯蚓、切开后短的蚯蚓分别放入三个队列，每次只需取三个队列中front的最大数，就是当前蚯蚓的最大长度另外为了统一，规定放进队列时的长度为这段蚯蚓在t=0时的长度，取出来时，只需增加相对应的取出时间，就能得到当前蚯蚓的实际长度。我是用了两个队列和一个优先队列，当然也可以将输入元素放在一个新开的数组a，用sort对a进行排序，再放进队列1中 #include <bits/stdc++.h> using namespa...

可以把a看成左括号，b看成右括号，这样判断是否为好串就能转化成括号匹配问题方法一：开栈。碰到左括号就入栈，右括号就出栈，使左右括号对应匹配，若有一次栈空（即左括号不够）但还有右括号，则右括号多了，不是好串。最终只要栈空，就是好串，否则不是好串方法二：计数。本题中只有一种括号，因此无需开栈，只需要记录当前的左右括号出现次数。具体说来，出现左括号时cnt++，出现右括号cnt--，如果cnt<0即不够减了，就不是好串。最终若cnt==0,就是好串，否则不是好串。 #include <bits/stdc++.h> using namespace std; int main(){ s...

二分k+差分检查 我们可以把每天能借的教室数量用数组存下来。当第i天到第j天需要借出k间教室时，a[i]到a[j]的数都减k。这样就能用差分数组来完成。若前k份订单可以，则前面k-1份都可以；若第k份不行，则后面都不行，因此想到二分每次都对前k份订单用差分数组维护，看看是否会减成负数 这里用的差分数组并不是严格意义上的差分，而可以理解成是相对于原数组的差分。例如，原数组a为1 2 8 3 5 （下标从1开始），现在需要把下标2到4的数都减1这时候，差分数组d可以表示为0 -1 0 0 1那么如何求之后的数组a呢？以a中下标0的元素为参照（假设它存在且保持不变），由于d[1]=0,因此a[1]相...

依然是典型的二分。如果可以凑成k张牌，则比k小的也能凑，这时候下界l变成mid+1；如果k张牌凑不成，则比k大的也不能凑，这时候上界变成mid-1.本题几个需要注意的代码细节：1.r的初值。极限状态下Ci最大5e8，同时J牌也是5e8，每组要么一张J牌要么一张Ci，能抽出1e9对牌。2.int的范围略大于2e9，但本题中需要对使用到的J牌数目叠加，就可能超范围了。所以在judge中计算J牌数目时，sum需要开long long.其他变量开int即可。3.最终答案是使得judge(mid)成立的最大的mid，也是最后一次判断成立的mid.因此，l-1就是最终答案。又因为走出22行的while循环...

这题几个小坑，调了很久才出来：1.注意k是吹风机和自然烘干的共同结果！减去1后才是吹风机的单独作用！2.需要对边界k==1特判 思路不会太难：本题相当于求晾干最长时间的最小值，可以考虑二分解决。若用时间x能晾干，则>x也能晾干，接下来只需考虑<x的部分。若用时x晾不干，则>x也不能晾干。二分的最终答案是使judge(mid)==1成立的最后一个mid，而跳出36行的while循环时，必有r+1==l，即r刚好跑到l左边。由于每次judge判断成立时r=mid-1，因此最终答案=mid=r+1=l #include <iostream> #include <s...

第一次写发现超时了，于是选择了30和50来打表 #include <bits stdc++.h> using namespace std; unsigned long long a[9]; unsigned long long sum; void Hanoi(int n,char pre,char zhong,char mu){ if(n==30){ a[(pre-'A')*3+zhong-'A']+=238609299; a[(pre-'A')*3+mu-'A']+=119304657; a[(zhong-'A')*3+pre-'A']+=119304642; a[(zhong-...

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; char oriLights1[4];//最初灯的状态1,b设为0，w设为1 char oriLights2[4];//最初灯的状态2,b设为1，w设为0 char Lights[4];//每次修改后灯的状态 int GetBit(char x,int i){//得到x的第i位 return (x>>i)&1; } void Se...

尺取法（双指针）例题。暴力算法就是两重for循环枚举i和j的位置。这里我们可以进行优化：①当i到j的和≥s时，j就不需要往后移动了；②当i变成i+1时，由于i到j-1的和小于s，i到j的和≥s，因此i+1到j-1的和一定小于s。也就是说，当i加1时，j只需后移一位即可开始新一轮的判断。这里从i到j的和，采用前缀和实现。注意，i到j的和是j的前缀和减去i-1的前缀和。令a[0]=0,sum[0]=0,i从1开始循环，这样a[i-1]就不会越界。代码如下： #include <bits/stdc++.h> using namespace std; typedef long long l...