大佬求助,除了最后一个全wa了,python生成的数据却全ac了
  • 板块学术版
  • 楼主xbdx
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/29 19:47
  • 上次更新2024/3/29 21:57:57
查看原帖
大佬求助,除了最后一个全wa了,python生成的数据却全ac了
1181666
xbdx楼主2024/3/29 19:47
#include <bits/stdc++.h>
using namespace std;

const int M = 2e5+10,N = 2e5+10;

int e[M],l[M],r[M],head,tail,sx[N];
bool st[N];
char sex[N];
int able[N]; 
int idx;


struct pi
{

    int ablility;
    int a,b;

    bool operator < (const pi & t) const
    {

        if(ablility != t.ablility)  return t.ablility < ablility;
        if(a != t.a)    return t.a < a;
        else    return t.b < b;

    }

};

priority_queue<pi> heap;

void new_double_link()
{

    head = -1;
    tail = -1;
    idx = 1; 

}

void insert(int x,char y)
{

    e[idx] = x;
    sx[idx] = y;

    if(tail != -1)
    {

        r[tail] = idx;

        l[idx] = tail;

        tail = idx++; 

    }

    else
    {

        l[idx] = -1;
        r[idx++] = -1;
        tail = 1;
        head = 1;

    }

}

void remove(int i)
{

    if(i == head)
    {

        int n = r[head];

        e[head] = r[head] = l[r[head]] = -1;

        head = n;

        // cout << l[n] << endl;
        return;

    }
    else if(i == tail)
    {

        int n = l[tail];
        e[tail] = l[tail] = r[l[tail]] = -1;
        head = n;

        // cout << l[n] << endl;
        return;
    }

    // cout << i << ' ';

    l[r[i]] = l[i];
    r[l[i]] = r[i];
    // cout << l[r[i]] << endl;

}

void judge(int x)
{
    if(x == -1) return;

    if(r[x] != -1)
    {

        if(sx[x] != sx[r[x]])
        {

            heap.push({abs(able[x] - able[r[x]]),x,r[x]});

        }

    }
    
    if(l[x] != -1)
    {

        if(sx[x] != sx[l[x]])
        {

            heap.push({abs(able[x] - able[l[x]]),x,l[x]});

        }

    }


}

int main()
{
    new_double_link();

    vector<pair<int,int>> ans;


    memset(l,-1,sizeof(l));

    memset(r,-1,sizeof(r));

    int n;

    cin >> n;

    for(int i = 1;i <= n;i++)
    {

        char c;
        while(scanf("%c",&c),c == ' ' || c == '\n');
        sex[i] = c;

    }

    for(int i = 1;i <= n;i++)
    {

        scanf("%d",&able[i]);
        insert(able[i],sex[i]);

    }

    // for(int i = head;i != -1;i = r[i])
    // {

    //     cout << e[i] << ' ';

    // }

    // cout << endl;

    




    for(int i = 1;i < n;i++)
    {   


        if(sex[i] != sex[i+1])
        {

            // cout << abs(able[i+1] - able[i]) << ' ';
            
            heap.push({abs(able[i+1] - able[i]),i,i+1});
            
            // cout << i << ' ' << i+1 << endl;
        }
    }



    while(!heap.empty())
    {

        pi t = heap.top();

        heap.pop();


        

        if(st[t.a] || st[t.b])
        {

            continue;

        }
       
        
        ans.push_back({t.a,t.b});

        st[t.a] = st[t.b] = 1;

        int left = l[t.a];

        int right = r[t.b];

        remove(t.a),remove(t.b);

        judge(left),judge(right);


    }



    cout << ans.size() << endl;

    for(auto i : ans)
    {

        int a = i.first,b = i.second;
        if(a > b)   swap(a,b);
         cout << a << ' ' << b  <<endl;
      

     

    }

    


}

已测试通过数据(一部分):

200 BGGGGGGGBGBBBBBGGGGBGBGGGGGGGGGGBBBGBBGGBBBGBGGGBGBGBBGGBBBGGGBBBBBGGBBBGGBBBBGGGBBGBBGBBBBBBGGBGBBGGGBGGBGGGGGGBGGGGBGBGGGBBGGGGGBGBGGBBBGBBBGBBBGBGBGGGBBGBBGBBBGGBBGBGGGGBBGGBBBGBGBBBBBGGGBBBBGGBBBG 593 7220 8519 5970 464 2894 1536 802 6958 3218 785 7963 6110 4188 3703 228 777 5726 5830 9295 7569 8653 7719 253 1479 6606 6701 4073 4290 4906 4499 6552 6006 3206 9890 5182 6963 9709 8110 7681 48 5626 3095 1497 8566 8748 4088 5858 6310 435 3044 9644 6232 4320 7599 5178 3779 9132 4284 66 8585 2881 9894 2160 1570 9446 8536 4896 6175 5357 3802 9789 83 924 3661 1822 7080 8688 3172 7088 6567 9909 8653 2383 1321 6794 8221 2254 7386 5753 8305 1412 7961 6695 4990 9596 5636 9113 7639 9615 4812 968 2511 2131 1860 6112 940 9189 1011 9039 1954 5614 6260 8703 4075 6306 7538 2277 1299 6475 8641 23 6691 7734 5458 980 5004 3765 3433 3737 1636 2025 9765 2330 2506 4931 9510 4843 5998 5470 5394 9943 910 9324 7979 6405 9025 9385 8471 9030 3717 7157 7132 4350 9133 3382 2282 469 7165 1417 193 913 8896 1227 3166 331 229 2721 2536 8259 3308 2719 1485 9046 5606 3595 4221 1100 7525 8190 7879 3871 2221 2771 4717 1984 3669 158 6342 6496 6590 9583 5020 1314 9548 3850 2708 6100 7893 3694

50 BGBGGGGGGGGGBGGBBBGBGBBBGBGGGBBGBGGBGBGBGBGGGBGGGG 2860 9676 9920 6053 5154 8648 5527 1139 5868 1799 6248 6782 9830 1809 9593 730 7346 1133 5164 5044 1518 8602 8442 9026 3110 8638 2224 4604 4339 6181 1832 3601 2648 5341 7391 7861 6119 6894 6988 7601 5361 3320 6557 1696 7997 4412 2309 5641 9548 2532

10 BBBBGGGBGG 7307 8479 9077 3850 4838 7181 5415 8296 2484 1237

2024/3/29 19:47
加载中...