16哈理工新生赛 B 修建传送门（双指针）

心已赠人 2022-07-14 09:29 58阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>题目链接：<a href="http://acm.hrbust.edu.cn/index.php?m=ProblemSet&amp;a=showProblem&amp;problem_id=2294" rel="nofollow">点击打开链接</a> 修建传送门</td> 
 </tr> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 1000 MS</td> 
 <td>Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table> 
 <tbody> 
 <tr> 
 <td>Total Submit: 104(29 users)</td> 
 <td>Total Accepted: 30(24 users)</td> 
 <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" alt=""></td> 
 <td>Special Judge: No</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 <tr> 
 <td>Description</td> 
 </tr> 
 <tr> 
 <td> &nbsp; &nbsp; &nbsp;做为长城上的卫士，影踪派一直守在螳螂高原上防止螳螂人卡拉克西的入侵。影踪派的长城可以近似看做是一条直线上依次编号为1~N的N个基地组成，编号相邻的两个基地之间由长城相连接，而影踪派掌门祝踏岚所在的影踪禅院位于编号为1的基地。 &nbsp; &nbsp;&nbsp;祝踏岚发现，每次螳螂人只会选择长城上的一个基地进行猛烈的攻击，所以，祝踏岚每次都要从影踪禅院赶到被攻击的基地亲临前线指挥战斗。但是，在长城上移动是很耗时的，为了能更快的赶到任何一个可能被攻击的基地，祝踏岚决定修建一对传送门。 &nbsp; &nbsp;&nbsp;一对传送门由两个入口组成，它能实现在两个入口间的瞬间转移。出于安全考虑，这两个入口一定要建造在基地上。祝踏岚想选出两个合适的基地建造这一对传送门，使得他从影踪禅院赶到任何一个基地所需要的移动距离最远的那个最短。（每次祝踏岚都会选择采用最短的方式前往每一个基地）。你能帮助他么？ 
 <div> 
 
 </div> </td> 
 </tr> 
 <tr> 
 <td>Input</td> 
 </tr> 
 <tr> 
 <td> 第一行为一个正整数T，表示测试数据组数。 每组测试数据第一行为一个整数N(1 &lt;= N &lt;= 100000)，第二行包含N-1个正整数，其中第i个数表示编号为i的基地与编号为i+1的基地之间的长城长度。此长度不会超过2147483647. </td> 
 </tr> 
 <tr> 
 <td>Output</td> 
 </tr> 
 <tr> 
 <td> 对每组测试数据输出一行，仅含一个整数，表示按照最优方案建造完虫洞后，祝踏岚需要从基地1赶到的移动距离最远的基地的移动距离。 </td> 
 </tr> 
 <tr> 
 <td>Sample Input</td> 
 </tr> 
 <tr> 
 <td> 2 3 1 20 6 1 2 3 4 5</td> 
 </tr> 
 <tr> 
 <td>Sample Output</td> 
 </tr> 
 <tr> 
 <td> 1 5</td> 
 </tr> 
 <tr> 
 <td>Source</td> 
 </tr> 
 <tr> 
 <td>2016级新生程序设计全国邀请赛</td> 
 </tr> 
 </tbody> 
</table>

题解：求从1赶到任何一个基地所需要的移动距离最远的那个最短.可以二分答案啊，也可以用双指针。预处理前缀和，即从1到每个点的距离。然后尺取法去枚举传送阵，第一个传送阵一定要放在1的位置上,否则最小的最大长度就是就会多了(1 -> 左边的传送阵)的距离. 所以dp\[i\]为前i个距离的前缀和。然后转移方程：

dis = max( max( dp\[ l - 1\], dp\[ i - 1 \] - dp\[ l \] ), dp\[ n-1 \] - dp\[ i-1\]); 表示第二个传送阵到两头的最大距离。

然后求最大的最小：ans =min( ans, dis );就可以了。

AC代码：

#include<cstdio>
 #include<iostream>
 #include<map>
 #include<algorithm>
 #include<cstring>
 typedef long long ll;
 using namespace std;
 ll dp[110000];
 int main()
 {
 
 	int t;
 	ll n;
 	cin>>t;
 	while(t--)
 	{
 		cin>>n;
 		memset(dp,0,sizeof(dp));
 		for(int i=1;i<n;i++)
 		{
 			ll a;
 			cin>>a;
 			dp[i]=dp[i-1]+a;
 	}
 	ll l=1;
 	ll ans=1e15;
 	ll dis=0;
 	//双指针 
 	for(int i=2;i<=n;i++) //枚举传送阵 
 	{
 		while(i > l && dp[i-1] - dp[l] > dp[l])
 		{
 			l++; 
 		}
 		dis=max( max( dp[l-1], dp[i-1]-dp[l] ), dp[n-1]-dp[i-1]);
 		ans=min(ans,dis);
 	}
 	 cout<<ans<<endl;
 }
 	return 0;
 }