C. Electrification

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

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

分析：这个题数据范围比较大。所以暴力一定不可以。  
我们可以先想一个简单一点的序列。  
给你一个n个数的序列。k = n - 1。那么这样的话，最优解一定是最小值+　最大值　的一半。这样可以使这个ｂ序列的第ｎ个值最小（想一下就清楚了）。然后我们就可以利用尺取得方法每次考虑（ｋ＋１）的长度的序列，每次求出最优解。不断更新即可。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int T,n,k;
    int a[200010],b[200010],b1[200010],b2[200010];
    
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d%d",&n,&k);
            for(int i = 1; i <= n; i ++)
                scanf("%I64d",&a[i]);
            k ++;
            ll M = 1000000101010;
            ll id;
            for(int i = k; i <= n; i ++)
            {
                int l = i - k + 1;
                int mid = (a[i] + a[l]) / 2;
                int maxx = max(mid - a[l],a[i] - mid);
                if(maxx < M)
                {
                   id = mid;
                   M = maxx;
                }
            }
            printf("%I64d\n",id);
        }
    }

[http_codeforces.com_contest_1175_problem_C]: http://codeforces.com/contest/1175/problem/C

发表评论取消回复

表情：

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

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

相关阅读

相关【C++】C/C++内存管理：

C/C++动态内存的底层原理深入浅出

怼烎@/ 2024年04月25日 20:19/ 0 赞/ 79 阅读

相关【C++】C/C++内存管理

文章目录 1. C/C++内存分布 2. C语言当中的动态内存管理 3. C++ 内存管理方式 3.1 new

╰+攻爆jí腚メ/ 2024年03月27日 17:00/ 0 赞/ 95 阅读

相关【c/c++】C++语言基础

基本内置类型相比于C语言增加的一些类型： <table> <tbody> <tr> <td colspan="1"> <p>类型</p> </td>

客官°小女子只卖身不卖艺/ 2023年10月04日 12:35/ 0 赞/ 76 阅读

相关【c/c++】C++初识

说明关于C++的内容，都是在已经了解了C语言的基础之上总结的，所以有不少C++的基础，因为也是C语言的基础，所以不会特意说明。输入输出首先是一个简单的例子：

Bertha 。/ 2023年10月04日 12:21/ 0 赞/ 25 阅读

相关 [转]C和C++混编,c调用C++,c++调用C

摘抄一: 1.引言　　C++语言的创建初衷是“a better C”，但是这并不意味着C++中类似[C语][C]言的[全局][Link 1]变量和函数所

绝地灬酷狼/ 2022年08月21日 09:59/ 0 赞/ 220 阅读

相关 c/c++整理--c++继承

一、c++继承关系理解请考虑下面标记为A~J的语句在编译时可能出现的情况，如果能够成功编译，请记为“RIGHT”，否则即为“ERROR” include <i

柔光的暖阳◎/ 2022年06月12日 07:21/ 0 赞/ 220 阅读

相关【C++】C++中的C

`C++`兼容`C`，但同样的东西，在`C++`和`C`中的表现可能不同，下面总结了一些。 1、函数空参 int f(); 函数空参时，`C`表示任意参数，`

绝地灬酷狼/ 2022年06月04日 07:40/ 0 赞/ 249 阅读

相关 C. Electrification

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

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

相关 C发展史：K&R C/C89/C99/C11 C++发展史： C++98/C++03/C++11

C语言的发展阶段 C语言之所以命名为C，是因为 C语言源自Ken Thompson发明的B语言，而 B语言则源自BCPL语言。 1. 1967年，剑桥大学的Marti

待我称王封你为后i/ 2021年07月28日 18:31/ 0 赞/ 529 阅读

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

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

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