【題解】Zerojudge f581 - 3. 圓環出口

AC (94ms, 1.9MB)

#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define gcd __gcd
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define clr clear
#define sz(x) (int)(x).size()
#define f first
#define s second
#define INF 1e9

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, d8j[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
const double pi = acos(-1);

const int mod = 1e9 + 7;

int n, m;
int pt[200000];
int s[200000];
int q;

int main(void) {
	fastio;
	cin >> n >> m;
	cin >> pt[0], s[0] = pt[0];
	for(int i = 1; i < n; i++) {
		cin >> pt[i];
		s[i] = s[i - 1] + pt[i];
	}
	int pos = 0;
	int cur_pt = 0;
	for(int i = 0; i < m; i++) {
		cin >> q;
		int lb = lower_bound(s, s + n, q + cur_pt) - s;
		if(lb != n) {
			pos = lb;
			cur_pt = s[lb];
		} else {
			cur_pt = s[n - 1] - s[pos];
			pos = 0;
			int lb2 = lower_bound(s, s + n, q - cur_pt) - s;
			pos = lb2;
			cur_pt = s[lb2];
		}
	}
	pos++;
	cout << pos % n << '\n';	
	
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge f581 - 3. 圓環出口