勵志用少的代碼做高效表達

---

貪心算法模板題

貪心算法簡單來講即自頂向下，求解出每個子最優解，且每個子問題不會對下一個問題產生影響

題意：n個人排隊接水，問如何排序才能使總等待時間最短，（正在接水的人和沒有接水的人都需要等待）

解法一、優先隊列，接水時間越短越靠前。

解法二、數組存儲+algorithm頭文件中的sort()升序排序，思路同上。
algorithm頭文件見我的這篇博客——>懶癌的福音_lgorithm頭文件函數全集

---

優先隊列解法代碼：

#include<bits/stdc++.h> //萬能頭文件 using namespace std; int main(){int n; while(cin>>n) { // priority_queue<int>q //從達到小 priority_queue<int, vector<int>, greater<int> >q; //從小到大 for(int i = 0; i < n; i++) {int x; cin>>x; q.push(x);}int len = q.size(), sum = 0;while(!q.empty()) {int num = q.top();sum += (len--)*num;q.pop();}cout << sum << endl;}return 0; }

---

數組解法代碼：

#include<bits/stdc++.h> //萬能頭文件 using namespace std; int a[1005]; int main(){int n; while(cin>>n) {memset(a,0,sizeof(a));for(int i = 0; i < n; i++) cin>>a[i];sort(a, a+n);int len = n, sum = 0;for(int i = 0; i < n; i++) {int num = a[i];sum += num*(len--); }cout << sum << endl;} return 0; }

總結

以上是生活随笔為你收集整理的17行代码AC_51Nod - 2133 排队接水（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。