Select solution language
Cho một mảng A gồm các phần tử nguyên với độ dài n và có q truy vấn. Mỗi truy vấn có dạng i, x, yêu cầu chèn giá trị x vào vị trí i của mảng A. Sau mỗi truy vấn, in ra mảng A.
n
và q
từ đầu vào. Tạo một mảng A
với n
phần tử từ đầu vào.i
và x
từ đầu vào.x
vào vị trí i
của mảng A
.A
sau khi chèn.O(n + q * m)
, trong đó m
là kích thước trung bình của mảng sau mỗi truy vấn. Điều này là do việc chèn vào vector có độ phức tạp trung bình là O(m)
./*
author: longvuu
github: kuronight29
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll n, q;
cin >> n >> q;
vector<ll> A;
for (ll i = 0; i < n; i++)
{
ll x;
cin >> x;
A.push_back(x);
}
for (ll i = 0; i < q; i++)
{
ll x, y;
cin >> x >> y;
A.insert(A.begin() + x-1, y);
for (ll j = 0; j < A.size(); j++)
{
cout << A[j] << " ";
}
cout << endl;
}
}
Cho một mảng A
gồm các phần tử nguyên với độ dài n
và có q
truy vấn. Mỗi truy vấn có dạng i
, x
, yêu cầu chèn giá trị x
vào vị trí i
của mảng A
. Sau mỗi truy vấn, in ra mảng A
. Do mảng là cấu trúc tĩnh và không hỗ trợ trực tiếp chèn phần tử giữa các vị trí, ta sử dụng danh sách liên kết đơn (linked list) để thực hiện bài toán hiệu quả hơn, đặc biệt với các thao tác chèn.
data
): Lưu giá trị của phần tử.next
): Trỏ đến nút tiếp theo trong danh sách.head
): Trỏ đến nút đầu tiên.x
vào đầu danh sách.x
vào cuối danh sách.i
: Chèn giá trị x
vào vị trí i
.i
= 1, chèn đầu danh sách.i
> số phần tử, chèn cuối danh sách.i
và chèn.n
và q
.n
phần tử vào cuối bằng addTail
.q
truy vấn:
Mỗi truy vấn có dạng i
, x
:insertAtIdx
để chèn giá trị x
tại vị trí i
.i
- 1 trong danh sách và thực hiện chèn.nullptr
và in giá trị từng nút.i
: O(n).q
truy vấn: O(q * n).#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Node {
ll data;
Node* pNext;
Node(ll val) : data(val), pNext(nullptr) {}
};
struct List {
Node* pHead;
List() : pHead(nullptr) {}
};
void addHead(List &L, ll val) {
Node *new_node = new Node(val);
new_node->pNext = L.pHead;
L.pHead = new_node;
}
void addTail(List &L, ll val) {
Node *new_node = new Node(val);
if (!L.pHead) {
L.pHead = new_node;
return;
}
Node *curr = L.pHead;
while (curr->pNext) {
curr = curr->pNext;
}
curr->pNext = new_node;
}
void insertAtIdx(List &L, ll idx, ll val) {
if (idx == 1) {
addHead(L, val);
return;
}
Node *curr = L.pHead;
Node *new_node = new Node(val);
idx--;
while (idx > 1 && curr) {
curr = curr->pNext;
idx--;
}
if (!curr) {
cout << "Index out of range.\n";
delete new_node;
return;
}
new_node->pNext = curr->pNext;
curr->pNext = new_node;
}
void printList(List &L) {
Node *curr = L.pHead;
while (curr) {
cout << curr->data << " ";
curr = curr->pNext;
}
cout << endl;
}
int main() {
ll n, q;
cin >> n >> q;
List L;
for (ll i = 0; i < n; i++) {
ll x;
cin >> x;
addTail(L, x);
}
for (ll i = 0; i < q; i++) {
ll x, y;
cin >> x >> y;
insertAtIdx(L, x, y);
printList(L);
}
return 0;
}