360笔试9.9
360笔试第一题： 一个数组，对前m个元素进行一系列升序或者降序排序后求现在数组
我想了半天 怎么优化 实在想不出来 直接摁排序，竟然过了。。。就不写代码了
360笔试第二题： 黑白棋， n个数组，每次反转【l，r】闭区间内的元素，问每次翻转后有多少个黑色
我最开始想用线段树但感觉空间复杂度过高；于是就用的队列+merge的想法，但是情况考虑的话比较复杂，最后没有写完。。。希望大佬们可以一起讨论一下呜呜
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <queue>
using namespace std;
//代表为白棋子的区间
struct Node
{
int l, r;
Node *next;
Node(int l_, int r_) : l(l_), r(r_) {}
};
int main()
{
int n, m;
cin >> n >> m;
int l, r;
Node *head = nullptr;
Node *now = nullptr, *pre = nullptr;
//白棋的个数
int count = 0;
for (int i = 0; i < m; i++)
{
cin >> l >> r;
pre = nullptr;
now = head;
while (now && l <= r)
{
// （） 插入的区间l，r， 【】当遍历的区间 now
// () []
if (r < now->l)
{
break;
}
//( [ ) ]
else if (l < now->l && r >= now->l && r <= now->r)
{
count -= r - now->l + 1;
int tmp = now->l;
now->l = r + 1;
r = tmp - 1;
if (now->l > now->r)
{
if (pre)
pre->next = now->next;
Node *temp = now->next;
delete now;
now = temp;
}
break;
}
//[ ( )]
else if (l >= now->l && r <= now->r)
{
count -= r - l + 1;
int tmp = now->l;
now->l = r + 1;
r = l - 1;
l = tmp;
if (now->l > now->r)
{
if (pre)
pre->next = now->next;
Node *temp = now->next;
delete now;
now = temp;
}
break;
}
//[ (] )
else if (l >= now->l && l <= now->r && r > now->r)
{
count -= now->r - l + 1;
int tmp = now->r;
now->r = l - 1;
l = tmp + 1;
if (now->l > now->r)
{
if (pre)
pre->next = now->next;
Node *temp = now->next;
delete now;
now = temp;
}
else
{
pre = now;
now = now->next;
}
}
//( [] )
else if (l < now->l && r > now->r)
{
count -= now->r - now->l + 1;
int tmp_r = now->r;
now->r = now->l - 1;
now->l = l;
l = tmp_r + 1;
pre = now;
now = now->next;
}
//[] ()
else if (l > now->r)
{
pre = now;
now = now->next;
}
}
if (l <= r)
{
Node *temp = new Node(l, r);
if (pre == nullptr)
{
temp->next = now;
head = temp;
}
else
{
pre->next = temp;
temp->next = now;
}
count += r - l + 1;
}
cout << n - count << endl;
}
while (head)
{
Node *temp =head;
head = head->next;
delete temp;
}
return 0;
} 笔试又要挂喽。。。
