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.|

P174SUMJ - ROUND 4J - Sắp xếp đơn giản

Phatom Assassin rất thích ăn chuối, những quả chuối có kích thước là a[i]. P.A được phép ăn hết N quả chuối nhưng cô sẽ rất phấn khích khi ăn được quả chuối to hơn quả chuối cô vừa ăn trước đó. Cho trước kích thước của N quả chuối hãy tìm cách sắp xếp lại vị trí của các quả chuối để khi P.A ăn lần lượt từ đầu đến cuối sẽ đạt được độ phấn khích lớn nhất tức là số cặp a[i]<a[i+1] là nhiều nhất.

Input

Dòng đầu là số N (1<=N<=1000)

Dòng tiếp theo gồm N số a[i] (1<=a[i]<=1000)

Output

Độ phấn khích lớn nhất có thể đạt được.

Example

Test 1:
Input:
5
2 4 1 3 5
Output: 4
Test 2:
Input:
6
8 8 8 8 8 8
Output:
0

Được gửi lên bởi:adm
Ngày:2017-08-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2021-08-16 11:23:55
#include<stdio.h>

void Sort(int a[], int n){
int i, j;
for(i=1; i<n; i=i+1){
int t = a[i];
j = i-1;
while(j >= 0 && a[j] > t){
a[j+1] = a[j];
j = j - 1;
}
a[j+1] = t;
}
}

int min(int arr[], int solan[], int u){
int i, min = 1000000;
for(i=0; i<u; i=i+1){
if(solan[arr[i]] < min && solan[arr[i]] > 0) min = solan[arr[i]];
}
return min;
}

int sophantu(int arr[], int solan[], int u){
int dem = 0, i;
for(i=0; i<u; i=i+1){
if(solan[arr[i]] > 0) dem = dem + 1;
}
return dem;
}

int a[1005], solan[1005];

void Xuat(int a[], int n){
int i, j, b[n], arr[n];
for(i=0; i<n; i=i+1) b[i] = 1;
for(i=0; i<1005; i=i+1) solan[i] = 0;
for(i=0; i<n; i=i+1){
scanf("%d", &a[i]);
solan[a[i]] = solan[a[i]] + 1;
}
Sort(a, n);
for(i=0; i<n; i=i+1){
if(b[i] == 1){
for(j=i+1; j<n; j=j+1){
if(a[j] == a[i]){
b[j] = 0;
}
}
}
}
int u = 0;
for(i=0; i<n; i=i+1){
if(b[i] == 1){
arr[u] = a[i];
u = u + 1;
}
}
int ans = 0;
for(i=0; i<u; i=i+1){
int m = min(arr, solan, u);
if(m > 0 && m < 1000000){
int spt = sophantu(arr, solan, u) - 1;
for(j=0; j<u; j=j+1){
if(solan[arr[j]] >= m) solan[arr[j]] = solan[arr[j]] - m;
}
ans = ans + m*spt;
}
}
printf("%d\n", ans);
}

int main(){
int n, i, j;
scanf("%d", &n);
Xuat(a, n);
}
2020-03-11 11:10:09
?

Last edit: 2020-03-24 12:00:27
2020-02-23 16:29:32
Hint: không phải sắp xếp bình thường đâu meow, tốn 13 măng cụt mới AC được đó meow :<
Chú Mèo Chui Xoong: meow
2020-02-01 20:32:51
sắp xếp đơn giản hiihi
2020-02-01 19:00:43
ko hiểu sai đâu
2018-07-24 16:38:06
-,- chả hiểu sao cứ sai hoài ta
2018-03-09 16:11:45
-_-. Đề quái vch??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.