KTLT 7) SỐ NGHỊCH THẾ

Tiêu đề: KTLT 7) SỐ NGHỊCH THẾ Tue May 10, 2022 4:41 pm

7) SỐ NGHỊCH THẾ
Xét dãy số nguyên A = (a1, a2, . . ., an,)(1 ≤ n ≤ 100 000). Các số trong dãy A khác nhau từng đôi một và nhận giá trị trong phạm vi từ 1 đến n. Như vậy dãy A là một hoán vị các số từ 1 đến n. Cặp số (ai, aj)trong dãy A được gọi là một nghịch thế, nếu i < j và ai > aj.
Yêu cầu: Cho n và hoán vị A. Hãy xác định số nghịch thế.
Dữ liệu: Vào từ file văn bản INVERS.INP:
• Dòng đầu tiên chứa số nguyên n,
• Dòng thứ 2 chứa n số nguyên xác định hoán vị A.
Kết quả: Đưa ra file văn bản INVERS.OUT một số nguyên – số lượng nghịch thế.
Ví dụ:
INVERS.INP
5
2 4 3 5 1
INVERS.OUT
5

Tiêu đề: Re: KTLT 7) SỐ NGHỊCH THẾ Thu May 12, 2022 4:33 pm

Thuật toán:
Subtask1:

Code:: for(i,1,n-1)
for(j,i+1,n)
nếu a[i] > a[j] thì res++
Đưa res.

Subtask2: ....

Tổng số bài gửi : 14 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>

#define maxn 100005
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("INVERS.INP","r",stdin);
freopen("INVERS.OUT","w",stdout);
int n,a[maxn],res=0;
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i] > a[j]) res++;
}
}
cout << res;
return 0;
}

Tổng số bài gửi : 14 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>

#define ll long long
using namespace std;

long long f[100600],ans;
int n, x;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("INVERS.INP","r",stdin);
freopen("INVERS.OUT","w",stdout);
cin >> n;
while (n--) {
cin >> x;
for (int i = x + 1; i <= 100000; i += i & -i) ans += f[i];
for (int i = x; i; i -= i & -i) f[i]++;
}
cout << ans << " ";
return 0;
}

Tổng số bài gửi : 71 Join date : 10/05/2022

Code:: /*Meliodasssf*/

#include<bits/stdc++.h>
using namespace std;
#define forl(i,a,b) for (int i=a; i<=b; i++)
#define forr(i,a,b) for (int i=a; i>=b; i--)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

int n,A[100001],res=0;

void nhap()
{
cin >> n;
forl(i,1,n) cin >> A[i];
}

int main ()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen ("in.txt","r",stdin);
// freopen ("out.txt","w",stdout);
nhap();
forl (i,1,n-1)
forl (j,i+1,n)
if (A[i] > A[j]) res++;
cout << res;
return 0;
}

Tổng số bài gửi : 34 Join date : 08/05/2022

#include<bits/stdc++.h.>
#define nmax 100007

using namespace std;

int n;
int a[nmax];

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("INVERS.inp", "r", stdin);
freopen("INVERS.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int d = 0;
for(int i = 1; i < n; i++){
for(int j = i+1; j <= n; j++)
if(a[i] > a[j]) d++;
}
cout << d;
return 0;
}

Tổng số bài gửi : 16 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>

#define maxc 100001
using namespace std;

int dem,n;

int a[maxc],c[maxc];

bool b[maxc];

void nhap()
{
cin>>n;
for(int i =1; i <= n; i++)
cin>>a[i];
}
void sol()
{
for(int i =1; i <= n - 1; i++)
for(int j = i + 1; j <= n; j++)
if(a[i] > a[j]) ++dem;
cout<<dem;
}
int main()
{
ios_base::sync_with_stdio(0);
nhap();
sol();
}

Tổng số bài gửi : 5 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
int n,a[100001],res=0;
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("invers.inp","r",stdin);
freopen("invers.out","w",stdout);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i] > a[j]) res++;
}
}
cout << res;
return 0;
}

Tổng số bài gửi : 34 Join date : 13/06/2022

Code:: #include <bits/stdc++.h>
#define nmax 100007

using namespace std;

int n,a[nmax],res=0;

void nhap()
{
cin >> n;
for(int i=1;i<=n;i++)
cin >> a[i];
}

void xuly()
{
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i] > a[j]) res++;
}
}
cout << res;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("INVERS.INP","r",stdin);
freopen("INVERS.OUT","w",stdout);
nhap();
xuly();
return 0;
}

» KTLT 8) SỐ ĐẸP
» KTLT 9) SỐ ĐẸP 2
» KTLT 6) Tìm ước nguyên tố
» KTLT 10) TÍCH CÁC CHỮ SỐ
» KTLT 5. Tổng 4 số nguyên tố