（新版）SJTU-OJ-1010. 逛商场

题目描述

听说许多同学国庆假期因为小作业爆肝到很晚！

听说有同学因此在逛商场的时候睡着了！

于是，为了让这位同学很快地买到自己想要的东西，我们规定：

商场一共有个货位，从入口到出口依次排列（别问我这是什么奇葩商场，就是有!），第个货位有件商品。而商场为了方便管理商品，给每件商品设定了一个编号。从商场入口走到这个商品一共有多少件商品，这个商品的编号就是多少。也就是说，第个货位中的第件商品的编号是.

该同学想要买件商品，已知这件商品的编号分别是，请你求出每件商品在第几个货位的第几个位置。

输入格式

第一行有两个整数，分别表示,.

第二行有个整数，分别表示.

第三行有个整数，分别表示​.

输出格式

一共有行，每行有两个整数，第行的第一个整数表示编号为​的商品在第几个货位，第二个整数表示这件商品在这个货位的第几个位置。

样例输入

样例输入 1

5 5
1 2 3 4 5
1 2 4 9 15

样例输入 2

5 5
2 3 5 2 1
8 5 10 4 1

样例输出

样例输出 1

1 1
2 1
3 1
4 3
5 5

样例输出 2

3 3
2 3
3 5
2 2
1 1

数据范围

.

.

.

题目吐槽

        国庆因为小作业，，嘶~

        我去年国庆可欢乐了，啥也没学。

        听说有同学因此在逛商场的时候睡着了！

        这是怎么做到的，那还不给我滚回寝室认真睡觉（不是）

        好扯的题目背景，明明知道学生这么辛苦，还出这种奇奇怪怪的题目。。。

        什么奇葩商场hhhh这也想得出来。。。我觉得这是菜市场而不是商场hhhh，淦！居然还找到图了

         这是正经的解析吗？

        嘶~

题目解答

        是时候正经啦，我先去oj那里考了一下古，发现了自己第一回写的代码，那真是一个无语啊

        考古结果：水平太差实在没办法hhhh，建议直接划走

        还是先看看最暴力的枚举法吧（反正当时我二分法不是很熟练2333）

        明显看得出来这是从左往右寻找的笨方法，用前缀和的方法明显更好，如果不会请走这里的传送门：

        一维二维数组前缀和 参考案例 (新版)SJTU-OJ-1008. LSZ的雪地脚印

        还是看看对的代码吧，每次输入一个区域就把前面一项的加上输入的这一项，放在新的数组空间里面

#include <iostream>
using namespace std;
int main()
{int m, n,c;cin >> n >> m;long long int input[n+1] = {0}, a[n+1] = {0};int wuwu[m+1];for (int i = 1; i <= n; i++){cin >> input[i];a[i] = a[i - 1] + input[i];}for (int x = 1; x <= m; x++){cin >> wuwu[x];}for (int x = 1; x <= m; x++){int l = 1, r = n;int mid;//cin >> c;c=wuwu[x];l = 1;r = n;while (l<=r){mid = (l + r) >> 1;if (a[mid] >= c && a[mid - 1] < c){cout << mid << " " << c - a[mid - 1] << endl;break;}if (c > a[mid])l = mid + 1;if (c <= a[mid - 1])r = mid - 1;}// 这一段while是最核心的语句，目标是为了查找mid// 且mid满足a[mid] >= c && a[mid - 1] < c}system("pause");return 0;
}

        思考：关于这个l还有r是我最头大的地方，加一减一的emmm

        不妨这样理解，首先，while里面有一个if判断，如果if判断过不了，那肯定当前的那个mid不行，不满足条件，那就要修正区间，区间只有两个可能：

        解释到这里应该很清楚啦，那就对号入座叭，稍微思考一下就可以得出答案。

        完结~

        怀念一下逛了两页的商场

        第二页逛商场