E. Queue Sort

这题教训主要是观察和思考

本来上来的想法就是链表加类似插排？但肉眼可见的tle....

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;


struct linknode
{
	linknode* next;
	ll val;
	linknode* prev;
	linknode() { val = 0; next = NULL; prev = NULL; }
};
bool is_not_del(linknode* s)
{
	linknode* rb = s;
	if (rb->next->val < rb->val)return false;
	rb = rb->next;
	while (rb->next != s)
	{
		if (rb->next->val < rb->val)return false;
		rb = rb->next;
	}
	return true;
}
void xg(linknode* s)
{
	linknode* p = s->next;
	linknode* pp = p->next;
	while (p != NULL)
	{
		delete p;
		p = pp;
		pp = pp->next;
	}
	return;
}
int main()
{
	ios::sync_with_stdio(false);//imp
	cin.tie(nullptr);//imp
	linknode* head;
	linknode* h = new linknode;
	head = h;
	int t; cin >> t;
	for (int iii = 0; iii < t; iii++)
	{
		int n; cin >> n;
		int xx;
		cin >> xx;
		h->val = xx;
		for (int ii = 1; ii < n; ii++)
		{
			cin >> xx;
			linknode* th = new linknode;
			h->next = th;
			th->prev = h;
			h = h->next;
			h->val = xx;
		}
		head->prev = h;
		h->next = head;
		int mintimes = 0;
		while (true)
		{
			ll thval = head->val;
			while (h->val >= thval and h!=head)h = h->prev;
			if (h == head)break;
			//插入节点
			if (h == head->prev)
			{
				head = head->next;
				h = head->prev;
			}
			else
			{
				h->next->prev = head;
				linknode* headn = h->next;
				linknode* hh = head->next;
				h->next = head;
				head->next->prev = head->prev;
				head->prev->next = head->next;
				head->prev = h;
				head->next = headn;
				head = hh;
				h = head->prev;
			}
			mintimes++;
		}
		if (is_not_del(head))cout << mintimes << endl;
		else cout << -1 << endl;
	}
	return 0;
}

但是通过观察和推理可以知道，当且仅当该列的最小元素后面有序的时候，这个才一定成立
因为每一次前面的插排到后面都不会改变原有的状态，如果后面不是满足要求的时候，那么插排再多次也没用
代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;

ll lst[200010];
int main()
{
	int t; cin >> t;
	for (int ii = 0; ii < t; ii++)
	{
		int n; cin >> n;
		ll minx = LLONG_MAX;
		ll minxid = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> lst[i];
			if (lst[i] < minx)
			{
				minxid = i;
				minx = lst[i];
			}
		}
		bool is_end = true;
		for (int i = minxid; i < n-1; i++)
		{
			if (lst[i + 1] < lst[i])
			{
				is_end = false;
				break;
			}
		}
		if (is_end)cout << minxid << endl;
		else cout << -1 << endl;
	}
	return 0;
}

总结：做题要带