Ntucoder – GAO – Siêu nhân GAO

1. Nội dung đề bài

• Dữ liệu vào: standard input
• Dữ liệu ra: standard output
• Giới hạn thời gian: 1.0 giây
• Giới hạn bộ nhớ: 128 megabyte

Các siêu nhân GAO gồm có 3 màu,  trắng (T), xanh (X) và đỏ (D). Ban đầu có tổng cộng n siêu nhân GAO đang sắp thành một hàng dọc với thứ tự màu lộn xộn. Khi có lệnh tập hợp, các siêu nhân phải đổi chỗ cho nhau (swap) sao cho màu trắng đứng đầu, màu xanh đứng giữa và màu đỏ đứng cuối. Bạn hãy tìm cách đổi chỗ các siêu nhân sao cho số lần đổi chỗ là ít nhất nhé.

Dữ liệu nhập:

– Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 10⁵).

– Dòng tiếp theo gồm n ký tự T, X, D thể hiện màu của các GAO trong thứ tự sắp hàng ban đầu. Đề bài cho đảm bảo có đủ 3 màu.

Dữ liệu xuất:

– Dòng đầu tiên là số m, là tổng số lần đổi chỗ ít nhất.

– Trong m dòng tiếp theo, mỗi dòng gồm 2 số i và j là chỉ số vị trí của 2 siêu nhân cần đổi chỗ. i và j cách nhau một khoảng trắng. Nếu có nhiều cách đổi chỗ, in ra một cách bất kỳ.

2. Hiểu đề bài như thế nào?

Nhiệm vụ chỉ là đổi chỗ Trắng đứng trước, xanh đứng giữa và đỏ đứng cuối. Và số lần đổi chỗ phải là ít nhất.

Ví dụ:

//input
6
XXTDDD

//output
1
1 3

//Với ví dụ này chỉ cần đổi chỗ 1 với 3 là đáp ứng yêu cầu

3. Cách tui giải và code

Ta nhập n là số lượng siêu nhân, man là chuỗi chứa màu của từng siêu nhân.
Từ chuỗi man ta tách thành từng ký tự và đếm xem có bao nhiêu ký tự T, bao nhiêu X và bao nhiêu D.

n=6  man=XXTDDD

d

1

2

3

Những giá trị T nào lớn hơn số lượng trắng + xanh ( > T+X ) thì lưu thành một mảng do phần tử dd[1][3] lưu lại. Còn những giá trị T nào ở giữa số lượng trắng và số lượng trắng + xanh ( T < K < T+X) thì lưu thành một mảng do phần tử dd[1][2] lưu lại.

Mình chỉ giải thích được tới đây thôi.

#include <bits/stdc++.h>
#define ii pair<int,int>
#define f first
#define s second
using namespace std;
int d[10];
vector<int>dd[9][9];
ii a[100007];

void xuatMangd()
{
	printf("\nMang d(soLuongTXD): ");
	for(int i =1; i<=3; i++)
		printf("%3d", d[i]);
	cout << endl;
}

void xuatMangdd()
{
	for(int i=0; i<9; i++)
		for(int j=0; j<9; j++)
		{
			if(dd[i][j].size()==0)
				cout << "rong"<<endl;
			else
			{
				for(int k=0; k<dd[i][j].size(); k++)
				{
					cout << "  " << dd[i][j].at(k);
				}
				cout << endl;
			}
		}
	cout << endl;
}

int main()
{
    //freopen("a.inp","r",stdin);
    //freopen("a.out","w",stdout);
    int n;
    cin>>n;
    string man;
    cin>>man;
    //cout<<man[24];
    int x,y;
    
    //cout << "n = " << n << "  man = " << man;
    
    for (int i=0; i<man.size(); i++)
    {
        if (man[i]=='T')
            d[1]++;
        if (man[i]=='X')
            d[2]++;
        if (man[i]=='D')
            d[3]++;
    }
    
    //xuatMangd();
    
    for (int i=0; i<man.size(); i++)
    {
        if (man[i]=='T')
        {
            if (i>=d[1]+d[2])
                dd[1][3].push_back(i);
        }
    }
    
    //xuatMangdd();
//        if (man[i]=='X')
//        {
//            if (i>=man.size()-1-d[3])
//                dd[2][3].push_back(i);
//        }
    for (int i=man.size()-1; i>=0; i--)
    {
        if (man[i]=='T')
        {
            if (i<=d[1]+d[2]-1&&i>=d[1])
                dd[1][2].push_back(i);
        }
    }
    //xuatMangdd();
//    sort(dd[1][2].begin(),dd[1][2].end());
    int tran=d[1];
    int dem=0;
    int w=0;
    while (w<=d[1]-1)
    {
        if (man[w]=='D')
        {

            if (dd[1][3].size()>0)
            {
                int j=dd[1][3][dd[1][3].size()-1];
                dd[1][3].pop_back();
                dem++;
                a[dem].f=w+1;
                a[dem].s=j+1;
                swap(man[w],man[j]);
                w++;
                x=dd[1][3].size();

            }
            else if (dd[1][2].size()>0)
            {
                int j=dd[1][2][dd[1][2].size()-1];
                dd[1][2].pop_back();
                dem++;
                a[dem].f=w+1;
                a[dem].s=j+1;
                swap(man[w],man[j]);
                w++;
                y=dd[1][2].size();
            }
        }
        else if (man[w]=='X')
        {
            if (dd[1][2].size()>0)
            {
                int j=dd[1][2][dd[1][2].size()-1];
                dd[1][2].pop_back();
                dem++;
                a[dem].f=w+1;
                a[dem].s=j+1;
                swap(man[w],man[j]);
                w++;
                y=dd[1][2].size();

            }
            else if (dd[1][3].size()>0)
            {
                int j=dd[1][3][dd[1][3].size()-1];
                dd[1][3].pop_back();
                dem++;
                a[dem].f=w+1;
                a[dem].s=j+1;
                swap(man[w],man[j]);
                w++;
                x=dd[1][3].size();
            }
        }
        else
        {
            w++;
        }
        //cout<<man<<"\n";
    }
    for (int i=w; i<man.size(); i++)
    {
        while (man[w]=='X')
            w++;
        if (man[i]=='X'&&i>=d[1]+d[2])
        {
            dem++;
            a[dem].f=i+1;
            a[dem].s=w+1;
            swap(man[i],man[w]);
            w++;
        }
    //cout<<man<<"\n";
    }
    cout<<dem<<"\n";
    for (int i=1; i<=dem; i++)
        cout<<a[i].f<<" "<<a[i].s<<"\n";
    return 0;
}

4. Các test case cho đề bài

#test1
//Input
6
XXTDDD
//Output
1
1 3

#test2
//Input
3
DTX
//Output
1
1 3

Kết Luận

Bài viết sau mình sẽ chia sẽ các bạn BANHCHUNG – Nấu bánh chưng nhé.