1046 Shortest Distance (20分)
The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.
Input Specification:
Each input file contains one test case. For each case, the first line contains an integer N (in [3]), followed by N integer distances D1 D2 ⋯ DN, where Di is the distance between the i-th and the (-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (≤), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 1.
Output Specification:
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
Sample Input:
5 1 2 4 14 9
3
1 3
2 5
4 1
Sample Output:
3
题目分析:刚开始的直接暴力做 第三个点没过 看了别人的博客 认识了前缀数组
10
7
错误代码
#define _CRT_SECURE_NO_WARNINGS
#include <climits>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
int Dist[];
int N, M;
int Sum;
void Ans(int i, int j)
{
int sum = ;
if (i > j)Ans(j, i);
else
{
for (int k = i; k < j; k++)
sum += Dist[k];
sum = (sum < (Sum - sum)) ? sum : Sum - sum;
cout << sum << endl;
}
}
int main()
{ cin >> N;
for (int i = ; i <= N; i++)
{
cin >> Dist[i];
Sum += Dist[i];
}
cin >> M;
int v1, v2;
for (int i = ; i < M; i++)
{
cin >> v1 >> v2;
Ans(v1, v2);
}
}
ac代码
#define _CRT_SECURE_NO_WARNINGS
#include <climits>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
vector<int>Dist;
int sum;
int main()
{
int N;
cin >> N;
Dist.resize(N + );
for (int i = ; i <=N; i++)
{
int temp;
cin >> temp;
sum += temp;
Dist[i] = sum;
}
int M;
cin >> M;
int v1, v2;
for (int i = ; i < M; i++)
{
cin >> v1 >> v2;
if (v1 > v2)
swap(v1,v2);
int s1 = Dist[v2 - ] - Dist[v1 - ];
int s2 = sum - s1;
if (s1 > s2)
cout << s2 << endl;
else
cout << s1 << endl;
}
}
最新文章
- chpasswd-批量修改用户密码
- 关于ajax为什么会返回php整个源码
- angularjs 下拉框
- JS,JQ点击事件
- postgresql copy命令介绍
- 如何在帝国cms后台菜单栏中添加删除链接?
- Difference between 2>;&;-, 2>;/dev/null, |&;, &;>;/dev/null and >;/dev/null 2>;&;1
- Ehcache(2.9.x) - API Developer Guide, Cache Usage Patterns
- Struts2 多文件下载
- GO实例3 Slice append打印
- POJ 3114 Countries in War(强连通+最短路)
- UIWebView 跳过HTTPS证书认证
- python基础-循环
- C# ExecutionContext 实现
- fastjson 反序列化漏洞利用总结
- norbert-构建服务器集群感知的 Java 应用程序
- linux常用命令:watch 命令
- elasticsearch term match multi_match区别
- nginx添加认证
- Node.js进程管理之子进程
热门文章
- CMAKE交叉编译快速入门
- HashMap 速描
- mysql实现读写分离
- 学妹问的Spring Bean常用配置,我用最通俗易懂的讲解让她学会了
- iframe 父框架调用子框架的函数
- Hadoop集群搭建(四)~centos6.8关闭防火墙
- webstorm 开新项目 setting 设置@目录别名 add @ (languages &; Framewors - Javascript - Webpack 4. setting eslint enable
- rem - 移动前端自适应适配布局解决方案和比较(转载)
- SQL的模糊查询(转载)
- 创建Sphinx + GitHub + ReadtheDocs托管文档