C. Electrification (贪心、思维、尺取)

深藏阁楼爱情的钟 2021-07-16 18:37 346阅读 0赞

[题目][Link 1]

思路：对于每个有k+1个元素的区间必然会存在一个x使得第k+1个元素-x为第k+1个最大，我们要想让这个结果最小则取(lst\[i\]+lst\[i+k\]+1)/2为x。即使这样求得的x可能不会使最近的x个元素刚好为此区间的，但这个x求得的最小值在之后的区间也会被另外的最小值给替换掉（具体原因可以模拟一下在该区间求得的x值有其它更近的元素情况），所以尺取遍历一遍即可。

#include<iostream>
    #include<string>
    #include<stdio.h>
    #include<map>
    #include<memory.h>
    #include<vector>
    #include<algorithm>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    typedef long long ll;
    using namespace std;
    const int Max = 1e6 + 5;
    int lst[Max], ls[Max];
    int n;
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, k;cin >> n >> k;
    		for (int i = 1;i <= n;i++)cin >> lst[i];
    		sort(lst + 1, lst + 1 + n);
    		int x=0, mi = 1e9;
    		for (int i = 1;i + k <= n;i++)
    		{ 
    			if ((lst[i + k] - lst[i]+1)/2 < mi)
    			{ 
    				x = (lst[i + k] + lst[i]) / 2, mi = (lst[i + k] - lst[i] + 1) / 2;
    			}
    		}
    		if (k == 0)cout << lst[1] << endl;
    		else cout << x << endl;
    	}
    
    }

[Link 1]: https://codeforc.es/contest/1175/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，346人围观）

还没有评论，来说两句吧...

相关阅读

相关尺取法总结

一般地，当我们要去枚举满足条件的区间权值的区间，可以用遍历双指针 l 和 r 的做法去枚举第一个满足条件的区间，然后去维护其他数据，这样的做法就是尺取法，它的复杂度为O(n)

矫情吗；*/ 2024年03月31日 15:50/ 0 赞/ 66 阅读

相关尺取法模板

题目描述博览馆正在展出由世上最佳的 M 位画家所画的图画。 wangjy想到博览馆去看这几位大师的作品。可是，那里的博览馆有一个很奇怪的规定，就是在购买门票

迈不过友情╰/ 2023年10月11日 10:42/ 0 赞/ 59 阅读

相关算法--尺取法

尺取法尺取法通常是指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点直到得出答案的方法，这种操作很像是尺取虫爬行的方式故得名。我们先来看看POJ的

￡神魔★判官ぃ/ 2022年08月21日 02:08/ 0 赞/ 186 阅读

相关 poj3320 尺取法~~

Jessica's Reading Problem <table> <tbody> <tr> <td><strong>Time Limit:</strong

红太狼/ 2022年08月09日 00:44/ 0 赞/ 175 阅读

相关 C. Electrification

题目链接： [http://codeforces.com/contest/1175/problem/C][http_codeforces.com_contest_1175_pr

太过爱你忘了你带给我的痛/ 2022年01月22日 10:45/ 0 赞/ 141 阅读

相关 C. Canine poetry (贪心、思维)

[题目][Link 1] 思路：首先可以知道如果我们要消灭长度>=4的回文串，那么这个大的回文串必然包含小的回文串。所以我们其实只要消灭小的回文串就可以了。其实就

谁借莪１个温暖的怀抱￠/ 2021年07月17日 01:19/ 0 赞/ 393 阅读

相关 C. Basic Diplomacy （思维、贪心）

[题目][Link 1] 思路：首先为NO的情况只有，某一天只可以选一个人且某人在只可以选他的情况下被选了>⌈m2⌉次。除了这种情况，其它情况不可能为NO，看一个极端的例

谁践踏了优雅/ 2021年07月16日 23:17/ 0 赞/ 409 阅读

相关 C. Maximum width (贪心、思维)

[题目][Link 1] 思路：对于答案我们只需求取每相邻的两个元素的最大相差再从所有的最大相差取最大的即可，那么贪心一下假如要求取的是第一个和第二个元素的最大相差，那么

朴灿烈づ我的快乐病毒、/ 2021年07月16日 23:12/ 0 赞/ 400 阅读

相关 C. Nauuo and Cards （贪心、思维）

[题目][Link 1] 思路：首先想能不能在原有的b中出现\ \ \ \ 1 2 3 … k，如果可以的话则利用b中原有的再添上前面的即可构成1 2 3 …n，但这个构

Bertha 。/ 2021年07月16日 18:53/ 0 赞/ 409 阅读

相关 C. Electrification (贪心、思维、尺取)

[题目][Link 1] 思路：对于每个有k+1个元素的区间必然会存在一个x使得第k+1个元素-x为第k+1个最大，我们要想让这个结果最小则取(lst\[i\]+lst\

深藏阁楼爱情的钟/ 2021年07月16日 18:37/ 0 赞/ 347 阅读