救救孩子 TLE

P1923 【深基9.例4】求第 k 小的数

可能性的世界 @ 2021-05-31 00:09:55

#include <iostream>
#include<stdio.h>
using namespace std;
struct link {
    int data;
    link* last;
    link* next;
};
int main()
{
    int a, b;
    link* head = NULL, * shift=NULL,*now=NULL;
    scanf("%d", &a);
    scanf("%d",&b);
    for (int x = 0; x < a; x++) {
        int k;
        if (x == 0) {
            head = new link;
            scanf("%d", &k);
            head->data=k;
            head->next = head->last = NULL;
            shift = head;
        }
        else {
            scanf("%d", &k);
            logo:
            if (k <= (shift->data)&&(shift->last==NULL)) {
                now = new link;
                now->next = shift;
                shift->last = now;
                now->last = NULL;
                now->data = k;
                head = shift = now;
                continue;
            }
            if ((k <= shift->data) && k>=(shift->last->data)) {
                now = new link;
                now->data = k;
                now->next = shift;
                now->last = shift->last;
                shift->last = now;
                now->last->next = now;
                shift = now;
                continue;
            }
            if (k >= (shift->data)&&(shift->next==NULL)) {
                now = new link;
                now->last = shift;
                shift->next = now;
                now->next = NULL;
                now->data = k;
                shift = now;
                continue;
            }
            if ((k >= shift->data) && k <= (shift->next->data)) {
                now = new link;
                now->data = k;
                now->last = shift;
                now->next = shift->next;
                shift->next = now;
                now->next->last = now;
                shift = now;
                continue;
            }
            if (k <= shift->data) {
                shift = shift->last;
                goto logo;
            }
            if (k >= shift->data) {
                shift = shift->next;
                goto logo;
            }
        }
    }
    shift = head;
    for (int z = 0; z < b; z++)
        shift = shift->next;
    printf("%d", shift->data);
}

刚学C++,不会分治,链表有破题办法吗?


by zhouyixian @ 2021-05-31 00:48:45

没有。

链表复杂度肯定不对。


|