二分求调

CPP 刷题王 2024-05-11 19:15:43 12
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node {
	int number, id;
	int prv, nxt;
}a[100010], b[100010];
struct loveccf {
	int id;   //未排序前的id
	int number; 
}tlhll[100010];
int tanLilyisHardWorking[100010];
bool cmp(loveccf smartkkksc03, loveccf smtcz) {
	if (smartkkksc03.number != smtcz.number)
		return smartkkksc03.number < smtcz.number;
	return smartkkksc03.id < smtcz.number;
}
map<int, int> toid;  //toid[bianliang] 存的是  bianliang 对应的结构体编号即 a[?] 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].id >> a[i].number;
		b[i].id = tanLilyisHardWorking[i] = a[i].id;
		tlhll[i].id = toid[a[i].id] = i;
		b[i].nxt = a[i].nxt = i + 1;
		a[i].prv = b[i].prv = i - 1;
		b[i].number = tlhll[i].number = a[i].number;
	}
	sort(tanLilyisHardWorking + 1, tanLilyisHardWorking + 1 + n);
	b[1].prv = b[n].nxt = a[1].prv = a[n].nxt = -1;
	sort(tlhll + 1, tlhll + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		int now = tlhll[i].id;
		if (b[now].prv != -1) {
			a[now].prv = b[now].prv;
		} else {
			a[now].prv = now;
		}
		if (b[now].nxt != -1) {
			a[now].nxt = b[now].nxt;
			if (b[now].prv != -1) {
				b[b[now].prv].nxt = b[now].nxt;
			}
			b[b[now].nxt].prv = b[now].prv;
		} else {
			b[b[now].prv].nxt = b[now].nxt;
			a[now].nxt = now;
		}
	}
/*
插叙:
如何找到第一个大于 now 的数的下标哩?
my 思路:无(呵呵哈哈哈 
*/ 
	int q, l, c;
	cin >> q;
	bool flag = 0;
	while (q--) {
		cin >> l >> c;   //有点晕,需要注释一下(蒟蒻) 第 l 个盒子是自 c 个盒子以来最大的 
		/*
		如果 l c 是在虚空上怎么办?
		答:二分找到第一个小于 l 的数,第一个小于 c 的数,
		并输出 meibi 或者 fosi 
		*/
		flag = 0;
		cout << toid[l] << endl;
		if (toid[l] == 0) {
			int ll = 1, rr = n, mid;
			while (ll < rr) {
				mid = ll + rr + 1 >> 1;
				if (tanLilyisHardWorking[mid] < l) {
					ll = mid;
				} else {
					rr = mid + 1;
				}
			}
			flag = 1;
			l = ll;
		} if (toid[c] == 0) {
			int ll = 1, rr = n, mid;
			while (ll < rr) {
				mid = ll + rr + 1 >> 1;
				if (tanLilyisHardWorking[mid] < c) {
					ll = mid;
				} else {
					rr = mid + 1;
				}
			}
			flag = 1;
			c = ll;
		}
		if (c > l) {
			if (a[toid[l]].nxt > toid[c] || a[toid[l]].nxt == toid[l]) {
				if (toid[c] - toid[l] == c - l && !flag) {
					cout << "true";
				} else {
					cout << "maybe";
				}
			} else {
				cout << "false";
			}
		} else {
			if (a[toid[l]].prv < toid[c] || a[toid[l]].prv == toid[l]) {
				if (toid[c] - toid[l] == c - l && !flag) {   //尽管是负数,但是还是相同 
					cout << "true";
				} else {
					cout << "maybe";
				}
			} else {
				cout << "false";
			}
		}
		cout << endl;
	}
	return 0;
}
/*
miaorunhao
上帝太渺小了
总分:待定
14:50 更改博客,总分:50
14:51 更改博客,总分:80~100
15:20 更改博客,总分:0  注释:TMd,如果序列是单调递增的请问阁下如何应对? 
17:07 更改博客,总分:100 
感谢 @maorunhao @CYJian @lclclcsu03 @uneh_2ne @大粪土 的贡献 

特别鸣谢
感谢 @IOI_ILJYT 的辛勤付出(very hard-working) 

# 解题思路
首先我们可以使用一个链表,其中包含前驱 prv,后继 nxt
盒子编号为 id 的值,

梦想:
*****王********前驱存的是第一个比 number 大且在 number 左边的盒子的编号
*****王********后继存的是第一个比 number 大且在 number 右边的盒子的编号(此处指结构体数组的编号) 
重中之重 ↑

最后对于每个询问,我们只需要写代码即可 
*/

只要不死循环就行

{{ vote && vote.total.up }}

共 5 条回复

CPP 刷题王

@shaobai ???

root 站长

啥不行 @shaobai

shaobai 老师
shaobai 老师

我们题库应该不行[doge]

CPP 刷题王