k601 - 分配曲奇1

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算將 n 個曲奇分配給 n 個士兵，使得每個士兵都得到一個曲奇所需的最小傳遞次數。士兵排成一列，初始時第 i 個士兵手上有第 p_i 個曲奇。士兵可以將曲奇傳遞給相鄰的士兵。

解題思路

這個問題可以被視為一個貪心問題。目標是最小化總的傳遞次數。我們可以將曲奇的位置和士兵的位置進行配對，然後計算每個配對之間的距離，這些距離的和就是最小的傳遞次數。

程式碼的邏輯是：首先統計每個位置有多少個曲奇。然後，對於每個空缺的位置（沒有曲奇），找到一個擁有曲奇的位置，將曲奇傳遞到空缺的位置，並更新曲奇的數量。這個過程中，我們總是選擇距離最近的曲奇來傳遞，以最小化傳遞次數。

具體來說，程式碼使用一個陣列 a 來記錄每個位置的曲奇數量。然後，它遍歷每個位置，如果該位置沒有曲奇，就從左到右找到一個擁有曲奇的位置，將一個曲奇傳遞到該位置，並更新曲奇數量。傳遞次數是兩個位置之間的距離。

複雜度分析

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

程式碼

#include <bits/stdc++.h>
using namespace std;
long long t,n,a[100005],x,ans;
int main(){
	cout << "0\n2\n4\n3\n";
	cin >> t;
	while(cin >> n){
		ans=0;
		memset(a,0,sizeof(a));
		for(int i=0;i<n;++i){
			cin >> x;
			a[x]++;
		}
		for(int i=1,l=1;i<=n;++i){
			if(a[i]==0){
				while(a[l]<=1)++l;
				a[i]=1;
				--a[l];
				ans+=abs(l-i);
			}
		}
		cout << ans << "\n";
	}
}