Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бодолт илгээх Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

RGB7753 - Чихэр

Алис нь цэцэрлэгийн багш бөгөөд ангийнхаа хүүхдүүдэд чихэр өгөхийг хүсэв.

Бүх хүүхдүүд нэг эгнээ болон суусан бөгөөд ангид үзүүлсэн гүйцэтгэлээсээ хамаараад тус бүр өөр өөрийн гэсэн оноотой.

Алис хүүхэд бүрт ядаж нэг чихэр өгөхийг хүсч байв.

Хэрэв зэргэлдээ суусан 2 хүүхдийн нэг нь илүү өндөр оноотой байвал тэр хүүхэд нөгөөгөөсөө олон чихэр авна.

Алис авч болох хамгийн бага хэмжээгээр чихэр авахыг хүсч байв.

Жишээлбэл хүүхдүүдийн оноо нь [4, 6, 4, 5, 6, 2] байвал Алис хүүхдүүдэд өгөх чихэр нь хамгийн бага байхаар дараах байдлаар өгч болно.

[1, 2, 1, 2, 3, 1]. Алис хамгийн багадаа 10 чихэр худалдаж авна.

Функцын тодорхойлолт

candies функыг гүйцээ. Алисын худалдаж авах хамгийн бага чихэрны тоог буцаана.

candies функцын параметер:

n: ангид байх хүүхдүүдийн тоо, integer

arr: integer тооноос бүрдсэн хүснэгт, хүүхэд бүрийн оноог илэрхийлнэ.

Оролтын формат

Эхний мөрөнд integer n байна. Хүснэгтийн хэмжээг илэрхийлнэ.

Дараагийн n тооны мөр болгонд arr[i] -н утга байна. i дугаар хүүхдийн оноог илэрхийлнэ.

Хязгаарлалт

1 <= n <= 105

1 <= arr[i] <= 105

Гаралтын формат

Алисын авч болох хамгийн бага чихэрны тоог заасан нэг мөр байна.

Жишээ оролт 0

3

1

2

2 

Жишээ гаралт 0

4

Тайлбар 0

Энд хүүхдүүдийн оноо нь 1, 2, 2 байна. Хэрэв 2 хүүхэд ижил оноотой байвал өөр тооны чихэр авч болно. Эндээс оновчтой тараалт нь 1, 2, 1 байна.

Жишээ оролт 1

10

2

4

2

6

1

7

8

9

2

1 

Жишээ гаралт 1 

19 

Тайлбар 1

Оновчтой тараалт нь 1, 2, 1, 2, 1, 2, 3, 4, 2, 1

Жишээ оролт 2

8
2
4
3
5
2
6
4
5

Жишээ гаралт 2

12

Тайлбар 2

Оновчтой тараалт нь 1, 2, 1, 2, 1, 2, 1, 2

 

Орчуулсан : Б.Баясгалантөгөлдөр АНУ

Submit solution!
Нэмсэн:Bataa
Огноо:2020-03-24
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:ADA95 ASM32 ASM64 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
Эх сурвалж:https://www.hackerrank.com/challenges/candies/problem
hide comments
2024-11-05 05:19:27
#include<bits/stdc++.h>
using namespace std;

int a[5000], b[100000], dp[5001];
int main() {

int n, m;
cin >> n >> m;

for ( int i = 0; i < n; i ++)
cin >> a[i];

sort(a, a + n);

for ( int j = 0; j < m; j ++)
cin >> b[j];

for ( int j = m - 2; j >= 0; j --)
b[j] = min(b[j], b[j + 1]);

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

int tmp = INT_MAX;
for ( int j = 0; j < i; j ++) {

tmp = min(tmp, dp[j] + b[a[i - 1] - a[j]]);
}

dp[i] = tmp;
}

cout << dp[n];
return 0;
}
2024-08-10 12:55:53
// Online C++ compiler to run C++ program online
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
int main() {
int n,i,b=0,c=0;
cin>>n;
vector<int> a(n+1);
for(i=0;i<n;i++){
cin>>a[i];
}
set<int>::iterator it;
set<int>::iterator itd;
set<int> s;
s.insert(a[0]);
for(i=1;i<n;i++){
it=s.lower_bound(a[i]);
if(it==s.end()){
s.insert(a[i]);
b++;
}else{
s.erase(a[c]);
s.insert(a[i]);
c++;


}
}
cout<<b;
return 0;
}




© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.