（新版）SJTU

（新版）SJTU

题目描述

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例输入

样例输入 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那里考了一下古，发现了自己第一回写的代码，那真是一个无语啊

评测编号	用户昵称	题目名称	评测状态	运行时间	内存	分数	语言	提交时间
47847		1010.逛商场	Wrong Answer	5378ms	23632KiB	40	C++	Jul-10-2021 19:44:08

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

Subtasks

Subtask1: 1 Score:10 Testpoint 1: Accepted Time Used: 54ms Mem Used:22400KiB Disk Usage: 0.01953125MiB Info: Subtask2: 2 Score:10 Testpoint 2: Accepted Time Used: 20ms Mem Used:22420KiB Disk Usage: 0.01953125MiB Info: Subtask3: 3 Score:10 Testpoint 3: Accepted Time Used: 25ms Mem Used:22420KiB Disk Usage: 0.01953125MiB Info: Subtask4: 4 Score:0 Testpoint 4: Wrong Answer Time Used: 22ms Mem Used:22420KiB Disk Usage: 0.01953125MiB Info: Subtask5: 5 Score:0 Testpoint 5: Wrong Answer Time Used: 15ms Mem Used:22420KiB Disk Usage: 0.01953125MiB Info: Subtask6: 6 Score:0 Testpoint 6: Wrong Answer Time Used: 18ms Mem Used:22420KiB Disk Usage: 0.01953125MiB Info: Subtask7: 7 Score:10 Testpoint 7: Accepted Time Used: 22ms Mem Used:22420KiB Disk Usage: 0.01953125MiB Info: Subtask8: 8 Score:0 Testpoint 8: Time Limit Exceed Time Used: 1785ms Mem Used:22424KiB Disk Usage: 0.0MiB Info: Time Limit Exceeded Subtask9: 9 Score:0 Testpoint 9: Time Limit Exceed Time Used: 1785ms Mem Used:22424KiB Disk Usage: 0.0MiB Info: Time Limit Exceeded Subtask10: 10 Score:0 Testpoint 10: Time Limit Exceed Time Used: 1873ms Mem Used:22424KiB Disk Usage: 0.0MiB Info: Time Limit Exceeded

        还是先看看最暴力的枚举法吧（反正当时我二分法不是很熟练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不行，不满足条件，那就要修正区间，区间只有两个可能：

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

        完结~

        怀念一下逛了两页的商场

评测编号	用户	题目名称	评测状态	运行时间	内存	语言	提交时间
47918		1010.逛商场	Accepted	627ms	22432KiB	C++	Jul-10-2021 22:53:37
47916		1010.逛商场	Accepted	862ms	22644KiB	C++	Jul-10-2021 22:52:55
47899		1010.逛商场	Wrong Answer	602ms	22660KiB	C++	Jul-10-2021 22:10:21
47892		1010.逛商场	Wrong Answer	589ms	22656KiB	C++	Jul-10-2021 22:01:45
47891		1010.逛商场	Wrong Answer	259ms	23016KiB	C++	Jul-10-2021 22:01:07
47890		1010.逛商场	Accepted	547ms	23012KiB	C++	Jul-10-2021 21:58:42
47888		1010.逛商场	Wrong Answer	565ms	22644KiB	C++	Jul-10-2021 21:58:09
47887		1010.逛商场	Wrong Answer	552ms	23008KiB	C++	Jul-10-2021 21:57:20
47886		1010.逛商场	Wrong Answer	856ms	22652KiB	C++	Jul-10-2021 21:56:21
47884		1010.逛商场	Accepted	584ms	23036KiB	C++	Jul-10-2021 21:49:33
47883		1010.逛商场	Wrong Answer	7974ms	22424KiB	C++	Jul-10-2021 21:49:02
47882		1010.逛商场	Wrong Answer	7747ms	23028KiB	C++	Jul-10-2021 21:47:24
47881		1010.逛商场	Wrong Answer	7644ms	23024KiB	C++	Jul-10-2021 21:45:36
47880		1010.逛商场	Accepted	605ms	22452KiB	C++	Jul-10-2021 21:44:12
47875		1010.逛商场	Wrong Answer	567ms	23060KiB	C++	Jul-10-2021 21:32:39

        第二页逛商场

评测编号	用户	题目名称	评测状态	运行时间	内存	语言	提交时间
47873		1010.逛商场	Accepted	578ms	22432KiB	C++	Jul-10-2021 21:28:58
47872		1010.逛商场	Compile Error	0ms	0KiB	C++	Jul-10-2021 21:27:33
47869		1010.逛商场	Wrong Answer	574ms	23040KiB	C++	Jul-10-2021 21:25:08
47867		1010.逛商场	Wrong Answer	535ms	22680KiB	C++	Jul-10-2021 21:20:05
47866		1010.逛商场	Accepted	765ms	22420KiB	C++	Jul-10-2021 21:19:01
47865		1010.逛商场	Wrong Answer	520ms	22440KiB	C++	Jul-10-2021 21:16:33
47864		1010.逛商场	Wrong Answer	597ms	22424KiB	C++	Jul-10-2021 21:13:51
47861		1010.逛商场	Wrong Answer	581ms	22424KiB	C++	Jul-10-2021 21:04:30
47860		1010.逛商场	Time Limit Exceed	9388ms	23028KiB	C++	Jul-10-2021 20:43:13
47859		1010.逛商场	Time Limit Exceed	9384ms	23024KiB	C++	Jul-10-2021 20:41:34
47858		1010.逛商场	Time Limit Exceed	10073ms	22424KiB	C++	Jul-10-2021 20:40:38
47856		1010.逛商场	Wrong Answer	594ms	23024KiB	C++	Jul-10-2021 20:37:48
47855		1010.逛商场	Wrong Answer	569ms	22416KiB	C++	Jul-10-2021 20:31:39
47854		1010.逛商场	Wrong Answer	545ms	23024KiB	C++	Jul-10-2021 20:27:58
47848		1010.逛商场	Wrong Answer	5625ms	22424KiB	C++	Jul-10-2021 19:45:12