思路：求平衡点，实际就是求一棵树的重心，我们只需要从上往下递归求出每一颗树的孩子的子树大小，模拟一个换根的过程，先把1当做根，记录下每一个节点的子树大小，在模拟换根的过程中，假设x为根，那么只需要记录一下它所有儿子的子树和以及n-其子树和中最大的值，然后取一个最小的最大值即可 #include <iostream> #include<stdio.h> #include<string> #include<string.h> #include<map> #include<queue> #include<deque>...

题意：有n张地毯，后铺的在最上面，给你一个点，问这个点最上面的地毯的编号是什么贪心方法：因为在最上面的地毯肯定在后面，所以我们只需要倒着找就可以了代码： #include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+10; typedef struct{ int a,b,x,y; }place; int main() { int n; place a[maxn]; ...

题意：n件物品，里面有一些凳子，有m个购物车，每个物品有一个权值a[i]和b[i],分别表示价值大小和是否为凳子，若一个购物车里有凳子，则这个购物车里的价格最高的物品半价贪心方法：我们可以发现有凳子除了影响半价没有其他影响了，所以我们只需要考虑一下有几个可以半价就可以了，于是我们就可以只计算一下购物车和凳子个数的最小值，然后找到最大的最小值的几个就行了，这几个用半价算，其他就直接加进去就好了代码： #include <iostream> #include<cmath> #include<vector> #include<algorithm> us...

题意：有n个点的完全无向图，每个点i有一个点权a[i],每两个点之间之间的边权大小为这两个点的点权和贪心方法：找到一个最小的点，要使得最后的结果最小，只需要把这个点和其他所有点连接的边权和求出即可代码： #include <iostream> #include<cmath> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+10; int a[maxn]; int main() { int n...

C:港口 思路 这个题是从差分数组的角度思考的。1.从差分数组的角度来看，每次对于区间[l,r]进行加操作就是对于差分数组cf[l]++,对cf[r+1]--;那么反过来思考，如果对原数组进行了区间[l,r]的加减操作，那么必然其差分数组一左一右分别进行了+1和-1的操作2.要使得原数组每个元素的大小都相同，即将**该数组的差分数组的每一个元素（除第一个外）都变成0**3.通过1和2两点，就把原题转化成了对差分数组的两点修改，所以最后我们只需求得怎么样可以在最小的改变次数下使得差分数组的所有值都为04.题目所求是最小操作数，应用贪心的思路，我们只需输出差分数组中正数的和以及负数和的绝对值中的最...