bestcoder 1002 Taking Bus

2024-08-24 12:58

文章标签 bus 1002 bestcoder taking

本文主要是介绍bestcoder 1002 Taking Bus，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1002 Taking Bus简单的分类讨论，设s,x,y分别表示公交的始发站，起点和终点。大概有这样几种情况：1. s≤x<y, 2. x<s<y，3. x<y≤s， 4. s≤y<x, 5. y<s<x, 6. y<x≤s分别写出公式即可。答案应该会超过int，注意要用long long。/************************************************ Author: fisty* Created Time: 2015/1/24 19:57:06* File Name   : BC-2.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define MAX_N 100100
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
LL d[2*MAX_N];
LL sum[2*MAX_N];int main(){//freopen("in.txt", "r", stdin);cin.tie(0);ios::sync_with_stdio(false);int t;cin >> t;while(t--){int n, m;cin >> n >> m;memset(d, 0, sizeof(d));memset(sum, 0, sizeof(sum));for(int i = 2;i <= n; i++){LL dis;cin >> dis;d[i] = dis;sum[i] = sum[i-1]+d[i];//Debug(sum[i]);}for(int i = 1; i <= n-1; i++){d[i+n] = d[n-i+1];sum[i+n] = sum[n+i-1] + d[i+n];}for(int i = 1;i <= m; i++){LL ans = 0;int x , y;cin >> x >> y;if(x > y){int end = n + (n-y);int start = ((i-1) % n)+1;//Debug(x);//Debug(y);if(start > x){ans = sum[n]-sum[start] + sum[n] - sum[x] + sum[x]-sum[y];}else{ans = sum[end] - sum[start];}}else{int start = ((i-1) % n)+1;if(start > x){ans = sum[y] + sum[n+n-1] - sum[start];}else{ans = sum[y] - sum[start];}}cout << ans << endl;}}return 0;
}