当前位置：首页 > news >正文

打卡信奥刷题（3369）用C++实现信奥题 P9691 [GDCPC 2023] Base Station Construction

news 2026/6/8 7:23:09

P9691 [GDCPC 2023] Base Station Construction

题目描述

中国移动通信集团广东有限公司深圳分公司（以下简称深圳移动）于199919991999年正式注册。四年后，广东省大学生程序设计竞赛第一次举办。深圳移动与广东省大学生程序设计竞赛一起见证了广东省计算机行业的兴旺与发展。

在建设通信线路的过程中，信号基站的选址是一个非常关键的问题。某城市从西到东的距离为nnn千米，工程师们已经考察了在从西往东1,2,⋯ ,n1, 2, \cdots, n1,2,⋯,n千米的位置建设基站的成本，分别是a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1,a2,⋯,an。

为了保证居民的通信质量，基站的选址还需要满足mmm条需求。第iii条需求可以用一对整数lil_ili和rir_iri表示（1≤li≤ri≤n1 \le l_i \le r_i \le n1≤li≤ri≤n），代表从西往东lil_ili千米到rir_iri千米的位置之间（含两端）至少需要建设111座基站。

作为总工程师，您需要决定基站的数量与位置，并计算满足所有需求的最小总成本。

输入格式

有多组测试数据。第一行输入一个整数TTT表示测试数据组数，对于每组测试数据：

第一行输入一个整数nnn（1≤n≤5×1051 \le n \le 5 \times 10^51≤n≤5×105）表示城市从西到东的距离。

第二行输入nnn个整数a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1,a2,⋯,an（1≤ai≤1091 \le a_i \le 10^91≤ai≤109），其中aia_iai表示在从西往东iii千米的位置建设基站的成本。

第三行输入一个整数mmm（1≤m≤5×1051 \le m \le 5 \times 10^51≤m≤5×105）表示需求的数量。

对于接下来mmm行，第iii行输入两个整数lil_ili和rir_iri（1≤li≤ri≤n1 \le l_i \le r_i \le n1≤li≤ri≤n）表示从西往东lil_ili千米到rir_iri千米的位置之间（含两端）至少需要建设111座基站。

保证所有数据nnn之和与mmm之和均不超过5×1055 \times 10^55×105。

输出格式

每组数据输出一行一个整数，表示满足所有需求的最小总成本。

【样例解释】

对于第一组样例数据，最优方案是在从西往东222千米和555千米的位置建设基站。总成本为2+100=1022 + 100 = 1022+100=102。

对于第二组样例数据，最优方案是在从西往东222千米和444千米的位置建设基站。总成本为3+2=53 + 2 = 53+2=5。

输入输出样例 #1

输入 #1

2 5 3 2 4 1 100 3 1 3 2 4 5 5 5 7 3 4 2 2 3 1 4 2 3 4 5

输出 #1

102 5

C++实现

#include<bits/stdc++.h>#defineMAXN500005usingnamespacestd;typedeflonglongLL;intn,m,a[MAXN];structSEG{intl,r;booloperator<(constSEG&B)const{returnr<B.r;}//将区间按右端点从小到大排序。}e[MAXN];LL f[MAXN];intq[MAXN],h,t;voidsolve(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);for(inti=1;i<=m;i++)scanf("%d%d",&e[i].l,&e[i].r);sort(e+1,e+m+1);intl=0;h=1,t=0,q[++t]=0;for(inti=1,j=1;i<=n;i++){f[i]=f[q[h]]+a[i];while(h<=t&&f[q[t]]>f[i])--t;//弹出不优的决策。q[++t]=i;for(;j<=m&&e[j].r<=i;j++)l=max(l,e[j].l);//双指针维护最大值。while(h<=t&&q[h]<l)++h;//排除过时决策。}printf("%lld\n",f[q[h]]);}intmain(){intT;scanf("%d",&T);while(T--)solve();return0;}