Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi Reja

#include
#include
using namespace std;
struct person{
string name;
int old, id;
};
int comp(person a, person b) {
return a.old < b.old || (a.old==b.old && a.id < b.id);
}


int main() {
int n;
cin>>n;
person a[n+1];
for (int i = 1; i <= n; i++) {
cin>>a[i].name>>a[i].old;
a[i].id = i;
}
sort(a+1, a+n+1, comp);
for (int i = 1; i <= n; i++) {
cout<}
}
4-misol
Elementlari soni n ta, 1 dan boshlab indekslangan bir o’lchamli massiv quyidagi formulabilan aniqlangan:
a_i = (b∙i²+c∙i+d) mod 2147483647;
Bu yerda “mod” amali qoldiq hisoblanadi. Sizning vazifangiz bu massiv elentlarinikamaymaslik tartibda saralab, saralangandan so’ng q ta so’rovga javob berish. Har bir i-so’rovda saralangan massivdagi k_i-o’rinda turgan elementning qiymatini chiqarishso’raladi.
Kiruvchi ma’lumotlar
Birinchi qatorda n va q sonlari berilgan(1≤n≤10⁶, 1≤q≤200). Ikkinchi qatorda b, c, d butun sonlari bitta probel bilan ajratib berilgan(1≤b,c,d ≤10⁴). Keyingi q ta qatordaso’rovlar berilgan. Har bir so’rov massivdagi nechanchi sonni chiqarish kerakliginiifodalovchi k_i sonidan iborat(1≤ k_i ≤n).
Chiquvchi ma’lumotlar
Dastlabki q ta satrda har bir so’rovga javobni ular berilish tartibida chiqaring.
Misollar

№	Kiruvchi ma’lumotlar	Chiquvchi ma’lumotlar
1	10 7 8 4 7 10 5 7 1 5 3 6	847 227 427 19 227 91 319

#include

using namespace std;
long long s[100001];
int z[100001];
long long binary_digit(int n, int m, long long degree){
if(m > 0){
degree *= n;
binary_digit(n, m - 1, degree);
}
else
return degree;
}
void qsort(int L, int R) {
int m = (L + R) / 2;
long long X = s[m];
int i = L;
int j = R;
while (i <= j) {
while (s[i] < X) i++;
while (s[j] > X) j--;
if (i <= j) {
swap(s[i], s[j]);
i++;
j--;
}
}
if (L < j) qsort(L, j);
if (i < R) qsort(i, R);
}
int main() {
long long d = binary_digit(2, 31, 1) - 1;
int n, q, a, b, c;
cin >> n >> q >> a >> b >> c;
for(int i = 1; i <= n; i++)
s[i] = (a * i * i + b * i + c) % d;
qsort(1, n);
for(int i = 1; i <= q; i++)
cin >> z[i];
for(int i = 1; i <= q; i++)
cout << s[z[i]] << endl;
}
4. Imtiyozli navbatlar va pyramidal saralash

Piramidani qayta tiklash amallari
Piramidaning muhim jihatlaridan biri bu, unda saqlanayotgan qiymatlarning maksimali uning tepasida joylashgan bo’ladi. Yuqorida keltirilgan faktlar bilan, ya’ni piramidani qayta tiklashning up() va down() amallari keltirilgandek piramidaning balandligidan oshmaydigan almashtirishlarni amalga oshiradi, bu esa ustuvor navbatlarni samarali qo’llashga imkon beradi.
Eng avvalo, bu qo’llash elementni tuzilmasini (chunki element faqat prioritetni emas balki qiymatni ham saqlaydi) tavsiflashni va piramida shakllantiriladigan massivni e’lon qilishni talab qiladi. Piramidani qayta tiklash amallari .priority maydonini solishtirishi lozim. Navbatning elementlari sonini saqlash uchun alohida size o’zgaruvchisi ajratiladi, konstruktorda unga 0 qiymati o’zlashtiriladi.
static const int MAX_SIZE = 100;
struct Elem {
int val;
int priority;
Elem(int v = 0, int p = 0) {
val = v;
priority = p;
}
} a[MAX_SIZE];
int size;
Element qo’shish a[size] yacheykasida amalga oshiriladi. Chunki qo’shish amalga oshirilgandan so’ng piramidaning asosiy xususiyati buzilishi mumkin, shuning uchun qo’shimcha ravishta up() protsedurasini chaqirish talab etiladi. Qo’shish amalining umumiy murakkabligi O(logN) ga teng.
void enqueue(int value, int priority) {
if (size + 1 == MAX_SIZE)
/* navbatni to’ldirishdagi hatolikni qayta ishlash */
a[size++] = Elem(value, priority);
up(size - 1);
}
O’chirishni esa quyidagicha amalga oshirish mumkin: piramidaning yuqorisiga uning eng oxirgi elementini joylashtirish va u uchun down() amalini bajarish. O’chirishning murakkabligi O(logN) ga teng.
int dequeue() {
if (size == 0)
/* hatolikni qayta ishlash – yechib olish uchun element mavjud emas */
swap(a[0], a[--size]);
down(0);
return a[size];
}

Quyida ustuvor navbatning qo’llanilishi bo’yicha to’liq kod keltirilgan. Navbat elementlarining to’lib ketishi yoki bo’sh navbatdan element yechib olishga urunishlar assert konstruksiyasi bilan beriladi (sarlavha fayli yoki ).
class PriorityQueue {

static const int MAX_SIZE = 100;

struct Elem {
int val;
int priority;
Elem(int v = 0, int p = 0) {
val = v;
priority = p;
}
} a[MAX_SIZE];
int size;

void up(int i) {

while (i != 0 && a[i].priority > a[(i - 1) / 2].priority) {
swap(a[i], a[(i - 1) / 2]);
i = (i - 1) / 2;
}
}

void down(int i) {

while (i < size / 2) {
int maxI = 2 * i + 1;
if (2 * i + 2 < size && a[2 * i + 2].priority > a[2 * i + 1].priority)
maxI = 2 * i + 2;
if (a[i].priority >= a[maxI].priority)
return;
swap(a[i], a[maxI]);
i = maxI;
}
}

public:

PriorityQueue() {
size = 0;
}

void enqueue(int value, int priority) {

assert(size + 1 < MAX_SIZE);
a[size++] = Elem(value, priority);
up(size - 1);
}

int dequeue() {

assert(size > 0);
swap(a[0], a[--size]);
down(0);
return a[size];
}

bool isEmpty() {

return size == 0;
}
};