徐州企业建站系统模板天津武清做网站

徐州企业建站系统模板,天津武清做网站,品牌建设 政策,开阿里巴巴网站建设流程思路分析 问题一#xff1a;求最小紧凑性 首先可以很容易发现#xff0c;紧凑性便是以横坐标最大和最小的两个摄像头画面的横轴距离为长、以纵坐标最小和最大的两个摄像头画面的纵轴距离为宽的矩形面积#xff0c;所以我们只需要让两者尽可能小就行了。 显然#xff0c;左…思路分析问题一求最小紧凑性首先可以很容易发现紧凑性便是以横坐标最大和最小的两个摄像头画面的横轴距离为长、以纵坐标最小和最大的两个摄像头画面的纵轴距离为宽的矩形面积所以我们只需要让两者尽可能小就行了。显然左右的移动和上下移动的这两类操作对于最终答案的贡献是分开的两者不会互相干扰。以题目第二组样例为例如图蓝色部分即为摄像头画面对于此时的图像画面而言紧凑性为。执行右移操作则画面变更为紧凑性变为。对于以上左移操作出现变化的只有横坐标最大和最小的两个摄像头画面的横轴距离而纵向并没有受到左移操作的影响。同理上下移动操作也不会影响到横向所以我们可以放心大胆地把横向和纵向分开讨论。仍以题目第二组样例为例先来看横向的。既然我们要求的是横坐标最大和最小的两个摄像头画面的横轴距离那我们不妨先给所有横坐标进行排序我们便得到了这么一个序列对应到图中则变成了这样tips重复的元素其实无所谓实际代码中去不去重不影响判断设最终答案的横长为不难发现当且仅当有元素从一个端点移动到另一个端点时才会发生变化其余步骤移动均不会改变的值。而从一个端点移动到另一个端点这一步骤我们既能通过左移来实现也能通过右移来实现。具体地如下图如果我想把左边的画面移动到最右边既可以通过左移一步来达成也可以通过右移三步来达成而其他的画面的位置会跟随其一并发生变化移动的方式最终不会影响到的值。所以先抛开右移操作仅考虑左移发生左右端点间的移动便是把中的值最小的点的值变化为其余的点的值则减去最小值。由于我们已经给排好序了所以其中的最小值便是了经过左移到左端点后再进行一次左移的操作后序列就会变成。我们再对其排一次序得到此时我们再代入求的公式便会得到。而如果把现在的序列再进行一次将最小值移动到右端点的操作我们又能得到一个新的。可以发现一共存在种可能的推到以下可得其中表示以原数组的第个数作为最小值时的值。带入到样例中我们能得到如下图所示的序列欸那怎么办呢我们只需要在最开始给排好序的时候直接就好啦因为本来就是这么多节点横坐标的最小值嘛于是这样我们就得到了所有可能的。相信这时候就有聪明的同学会想到题目要求的明明是最小值的紧凑性那我直接维护最小的不就行了吗费这个空间把所有存下来干嘛没错我们在枚举所有的时仅需要维护最小的那个就可以了没必要保留其他那些没什么用处的数据纵向上同理设最终答案的纵长为同相同的方法挨个枚举可能的并记录最小值就行。这样我们就解决了第一个问题。问题二达成最小紧凑性时的步数别忘了题目还有一个问题呢前面我们在求最小紧凑性的时候已经锁定了最小的和的值并且在枚举两者的时候找到了它们对应的点的坐标位置那我们不妨在枚举的同时再额外考虑一下如何到达这个问题。依旧以样例二、横向操作为例前文提到“ 从一个端点移动到另一个端点这一步骤我们既能通过左移来实现也能通过右移来实现 ”具体地想让数组中的最小值成为最大值可以通过将其左移到左界并再次左移或者是将其一直右移直至右界素材复用但仅仅只有这两种方法了吗并不一定。仔细思考可以发现对于每个枚举时我们的目的仅仅只是让最左端点移动成为数组中的最大值而不一定是让它成为右界。样例二并不能很好地体现这一点我们换一张图显然我们在考虑最左边的右移成为最大值时其实只需要右移两次、把右移超过右界来到左界就可以了并不需要把移动到最右端所以 让最左端点移动成为数组中的最大值 这个问题也可以转变为 让最左端点右侧的第一个端点移动成为数组中的最小值。面对转换后的问题最简单的方式不就是把这家伙给弄到左端点的位置上去吗而这又有了左移和右移两种方法。于是我们可以得到对于每个最简单地达成它一共有四种方式即四种移动步骤1.将左移至左端点的位置再左移一次步数2.将右移至右端点的位置步数3.将左移至左端点的位置步数4.将右移至右端点的位置再右移一次步数由于题目需要的是最小步数所以我们就取这四个值里头最小的那个作为对应的步数就可以啦纵向也是一个道理最后输出答案的时候输出最小的和最小的相乘的结果和他们对应的最小步数相加就完工啦恭喜你切了这道题最后进点食十年OI________不开________见祖宗Code#includebits/stdc.husing namespace std;const int MAXK1e55;#define int long longint h,w,k,x[MAXK],y[MAXK]; //x[]对应横坐标即文中的ay[]对应纵坐标int min_x,min_y,min_stepx0,min_stepy0; //min_x、min_y分别是最小的X和最小的Ymin_stepx和min_stepy则分别对应X和Y最小时的步数signed main(){cinhwk;for(int i1;ik;i)cinx[i]y[i];if(k1) //这里加了个特判因为就一个点的时候答案是一定的再跑一遍程序浪费时间其实加不加无所谓{cout1 0;return 0;}sort(x1,x1k);sort(y1,y1k);min_xx[k]-x[1]1;min_yy[k]-y[1]1;for(int i1;ik;i){if(min_x(h-(x[i]-x[i-1])1))min_stepxmin(min_stepx,min(x[i-1],min(h-x[i-1],min((x[i]-1),(h-x[i]1)))));else{min_xmin(min_x,(h-(x[i]-x[i-1])1));if(min_x(h-(x[i]-x[i-1])1))min_stepxmin(x[i-1],min(h-x[i-1],min((x[i]-1),(h-x[i]1))));}if(min_y(w-(y[i]-y[i-1])1))min_stepymin(min_stepy,min(y[i-1],min(w-y[i-1],min((y[i]-1),(w-y[i]1)))));else{min_ymin(min_y,(w-(y[i]-y[i-1])1));if(min_y(w-(y[i]-y[i-1])1))min_stepymin(y[i-1],min(w-y[i-1],min((y[i]-1),(w-y[i]1))));}}cout(min_x*min_y) (min_stepxmin_stepy);return 0;}