i855 - 01260 - Sales

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個銷售列表 A，要求計算一個列表 B 的數字總和。B 列表的第 i 個元素表示 A 列表中，在第 i 個元素之前（不包含第 i 個元素）有多少個元素小於或等於第 i 個元素。最終輸出 B 列表中所有元素的總和。

解題思路

題目要求計算每個元素前面有多少個小於等於它的元素，然後將這些數量加總。程式碼使用兩個巢狀迴圈來實現這個功能。外層迴圈遍歷銷售列表 A 的每個元素，內層迴圈遍歷該元素之前的所有元素，並檢查是否小於或等於當前元素。如果滿足條件，則將計數器 ans 增加。最後，輸出 ans 的值。

複雜度分析

• 時間複雜度: O(n^2)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	int t,n,a[1001],ans,i;
	for(cin >> t;t--;cout << ans << "\n"){
		cin >> n;
		for(i=0,ans=0;i<n;++i){
			cin >> a[i];
			for(int j=0;j<i;++j)
				if(a[j]<=a[i])++ans;
		}
	}
}