POJ3617

Best Cow Line

題意

給定長度為N的字符串S，要構造一個長度為N的字符串T。起初，T是一個空串，隨后反復進行下列任意操作：
從S的頭部（或尾部）刪除一個字符，加到T的尾部
目標是構造字典序盡可能小的字符串T。

思路

貪心算法，不斷取S的開頭和末尾中較小的一個字符放到T的末尾。但對于S的開頭和末尾字符相同的情況下，需要比較下一個字符大小，這可以用如下算法實現：
按照字典序比較S和S翻轉后的字符串S1，如果S較小，則從S的開頭取，否則從末尾取。

代碼

Source CodeProblem: 3617 User: liangrx06 Memory: 728K Time: 47MS Language: G++ Result: Accepted Source Code #include <iostream> #include <cstdio> #include <algorithm> using namespace std;#define N 2000int main(void) {int n, i, j, k, ii, jj;char s[N+1], t[N+1];while (cin >> n){for (i=0; i<n; i++) {getchar();scanf("%c", &s[i]);}s[i] = '\0';i = 0;j = n-1;k = 0;while (i <= j) {ii = i, jj = j;while (ii <= jj) {if (s[ii] != s[jj])break;ii ++;jj --;}if (ii <= jj && s[ii] > s[jj]) {t[k++] = s[j];j --;}else {t[k++] = s[i];i ++;}}t[k] = '\0';for (i = 0; i < n; i++){printf("%c", t[i]);if (i % 80 == 79) printf("\n");}if (n % 80) printf("\n");}return 0; }

POJ3069

Saruman’s Army

題意

這個題是說給你n個點，然后讓你標記其中盡可能少的點，使得n個點都處于被標記點左右不超過R的區間內。

思路

貪心法求解，從左到右選擇。

代碼

Source CodeProblem: 3069 User: liangrx06 Memory: 748K Time: 125MS Language: G++ Result: Accepted Source Code #include <iostream> #include <cstdio> #include <algorithm> using namespace std;#define N 1000int main(void) {int r, n, i, j;int pos[N], res;while (cin >> r >> n) {if (r == -1 && n == -1)break;for (i=0; i<n; i++)cin >> pos[i];sort(pos, pos+n);res = 0;i = 0;while (i < n) {j = i+1;while (j < n && pos[j] - pos[i] <= r)j ++;j --;i = j+1;while (i < n && pos[i] - pos[j] <= r)i ++;res ++;}cout << res << endl;}return 0; }

POJ3253

Fence Repair

題意

有一個農夫要把一個木板鉅成幾塊給定長度的小木板，每次鋸都要收取一定費用，這個費用就是當前鋸的這個木版的長度。給定各個要求的小木板的長度，及小木板的個數n，求最小費用。
提示：
以
3
5 8 5
為例：
先從無限長的木板上鋸下長度為 21 的木板，花費 21
再從長度為21的木板上鋸下長度為5的木板，花費5
再從長度為16的木板上鋸下長度為8的木板，花費8
總花費 = 21+5+8 =34

思路

利用Huffman思想，要使總費用最小，那么每次只選取最小長度的兩塊木板相加，再把這些“和”累加到總費用中即可
本題雖然利用了Huffman思想，但是直接用HuffmanTree做會超時，可以用優先隊列做

代碼

Source CodeProblem: 3253 User: liangrx06 Memory: 1184K Time: 219MS Language: C++ Result: Accepted Source Code #include <iostream> #include <cstdio> #include <algorithm> #include <set> using namespace std;int main(void) {int n, i;long long x, sum;multiset <long long> plank;while (cin >> n){for (i=0; i<n; i++) {cin >> x;plank.insert(x);}sum = 0;while (plank.size() > 1){x = *(plank.begin()) + *(++plank.begin());sum += x;plank.erase(plank.begin());plank.erase(plank.begin());plank.insert(x);}cout << sum << endl;plank.clear();}return 0; }

POJ2393

Yogurt factory

題意

有n周，第i周：需要向外供貨yi，生產1單位成本ci。若非本周生產的貨物不在本周銷售，需要貯藏，1單位貯藏一周需要花費s。問n周供貨供需花費多少錢（成本和貯藏費）。

思路

貪心，我們用minc記錄當前的最小單價，然后以最小單價買入，這個最小單價，要么是現在的單價，要么是之前的最小單價＋貯藏費。minc中被替換掉的值是不可能是以后的最小單價的。因為現在被替換，同時＋上若干個s之后它還是會比現在替換它的那個值大。

代碼

Source CodeProblem: 2393 User: liangrx06 Memory: 132K Time: 16MS Language: C++ Result: Accepted Source Code #include<iostream> using namespace std;int main() {int n, s, minc = 9999;scanf("%d %d", &n, &s);long long sum = 0;while(n --){int c, y;scanf("%d %d", &c, &y);if(c > minc + s)c = minc + s;minc = c;sum += c * y;}printf("%lld\n", sum);return 0; }

POJ1017

Packets

題意

問題描述
一個工廠制造的產品形狀都是長方體，它們的高度都是h，長和寬都相等，一共有六個
型號，他們的長寬分別為 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. 這些產品通常使用一個 6*6*h
的長方體包裹包裝然后郵寄給客戶。因為郵費很貴，所以工廠要想方設法的減小每個訂單運送時的
包裹數量。他們很需要有一個好的程序幫他們解決這個問題從而節省費用。現在這個程序由
你來設計。
輸入數據
輸入文件包括幾行，每一行代表一個訂單。每個訂單里的一行包括六個整數，中間用空
格隔開，分別為 1*1 至6*6 這六種產品的數量。輸入文件將以 6 個0 組成的一行結尾。
輸出要求
除了輸入的最后一行6 個0 以外，輸入文件里每一行對應著輸出文件的一行，每一行輸
出一個整數代表對應的訂單所需的最小包裹數。
輸入樣例
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
輸出樣例
2
1

思路

這個問題描述得比較清楚，我們在這里只解釋一下輸入輸出樣例：共有兩組有效輸入， 第一組表示有4 個3*3 的產品和一個6*6 的產品，此時4 個 3*3 的產品占用一個箱子，另外 一個 6*6 的產品占用 1 個箱子，所以箱子數是 2；第二組表示有7 個 1*1 的產品，5 個 2*2 的產品和1 個 3*3 的產品，我們可以把他們統統放在一個箱子中，所以輸出是1。
分析六個型號的產品占用箱子的具體情況如下：6*6的產品每個會占用一個完整的箱 子，并且沒有空余空間；5*5 的產品每個占用一個新的箱子，并且留下 11 個可以盛放 1*1 的產品的空余空間；4*4 的產品每個占用一個新的箱子，并且留下5 個可以盛放2*2 的產品 的空余空間；3*3 的產品情況比較復雜，首先3*3 的產品不能放在原來盛有5*5 或者4*4 的箱子中，那么必須為3*3 的產品另開新的箱子，新開的箱子數目等于3*3 的產品的數目除以 4 向上取整；同時我們需要討論為3*3 的產品新開箱子時，剩余的空間可以盛放多少2*2 和 1*1 的產品（這里如果有空間可以盛放2*2 的產品，我們就將它計入2*2 的空余空間，等到 2*2 的產品全部裝完，如果還有2*2 的空間剩余，再將它們轉換成 1*1 的剩余空間）。我們 可以分情況討論為3*3 的產品打開的新箱子中剩余的空位，共為四種情況：第一種，3*3 的 產品的數目正好是4 的倍數，所以沒有空余空間；第二種，3*3 的產品數目是4 的倍數加1， 這時還剩 5 個2*2 的空位和7 個 1*1 的空位；第三種，3*3 的產品數目是4 的倍數加2，這時還剩3 個2*2 的空位和6 個 1*1 的空位；第四種，3*3 的產品數目是4的倍數加3，這時 還剩 1 個 2*2 的空位和5 個 1*1 的空位；處理完3*3 的產品，就可以比較一下剩余的2*2 的空位和2*2 產品的數目，如果產品數目多，就將2*2 的空位全部填滿，再為2*2 的產品打開新箱子，同時計算新箱子中 1*1 的空位，如果剩余空位多，就將2*2 的產品全部填入2*2的空位，再將剩余的 2*2 的空位轉換成 1*1 的空位；最后處理 1*1 的產品，比較一下 1*1的空位與1*1 的產品數目，如果空位多，將1*1 的產品全部填入空位，否則，先將1*1 的空位填滿，然后再為 1*1 的產品打開新的箱子。

代碼

Source CodeProblem: 1017 User: liangrx06 Memory: 132K Time: 16MS Language: C++ Result: Accepted Source Code #include <iostream> #include <cstdio> #include <algorithm> using namespace std;bool input(int a[]) {bool flag = false;for (int i = 1; i <= 6; i ++) {scanf("%d", &a[i]);if (a[i] != 0) flag = true;}return flag; }int main(void) {int a[7];int i, k, m, res;while (input(a)) {res = 0;for (i = 6; i >= 1; i --) {k = (6/i)*(6/i);//每個包裹能放的第i個產品的數量m = a[i]/k;//需要的包裹數量a[i] %= k;int n1 = 6*6*m - i*i*m*k;//剩下多少個1*1if (a[i]) n1 += 6*6 - i*i*a[i];if (i == 3 || i == 4) {int n2 = 0;//剩下多少個2*2if (i == 4)n2 += 5*m;else if (i == 3 && a[i])n2 += (4-a[i])*2 - 1;if (n2 > a[2])n2 = a[2];a[2] -= n2;//printf("n1=%d, n2=%d\n", n1, n2);n1 -= 2*2*n2;//printf("n1=%d, n2=%d\n", n1, n2);}if ( i >= 2 && i <= 5 ) {if (n1 > a[1])n1 = a[1];a[1] -= n1;}//for (int x = 1; x <= 6; x ++)// printf("%d ", a[x]);//printf("\n");res += m;if (a[i])res ++;a[i] = 0;}printf("%d\n", res);}return 0; }

POJ3040

Allowance

題意

有N種不同面額的紙幣，你雇傭的一個人，每次支付至少C圓。每種紙幣的面額大小為V（每種紙幣的大小成整倍數關系這是結題的關鍵），張數為B，問你最多能支付多少次？

思路

將V從小到大進行一個排列

1.先把大于C元的紙幣用了，進行一個計數

2.再從大的紙幣進行抓取，抓得越多越好，但要小于等于C，如果等于C進行一個計數，如果小于C，再將紙幣從小的抓取，大于C進行一個計數。因為紙幣是成倍數關系的，你最大的紙幣面額，比前面所有紙幣面額加起來都大。

3.最后進行一個支付情況的總加，意思是，你后面還能像這第2步這樣支付方案的個數，然后再從第2步開始，直到不能支付。

代碼

Source CodeProblem: 3040 User: liangrx06 Memory: 212K Time: 16MS Language: C++ Result: Accepted Source Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int N = 20;struct Coin {int v, b; };bool cmp(const Coin &x, const Coin &y) {return x.v < y.v; }int n, c; int m[N]; Coin coin[N];int sum; bool choose(int i) {m[i] = sum / coin[i].v;if (m[i] > coin[i].b)m[i] = coin[i].b;sum -= m[i]*coin[i].v;if (sum == 0)return true;if (i == 0 || choose(i-1) == false) {if (coin[i].b > m[i]) {sum -= coin[i].v;m[i] ++;return (sum <= 0);}return false;}return true; }bool canPay() {memset(m, 0, sizeof(m));sum = c;return choose(n-1); }int main(void) {int i;cin >> n >> c;for (i = 0; i < n; i ++)cin >> coin[i].v >> coin[i].b;sort(coin, coin+n, cmp);int res = 0;while (canPay()) {int k = (int)1e9;//for (i = 0; i < n; i ++)// printf("%d ", m[i]);//printf("\n");for (i = 0; i < n; i ++) {if (m[i] > 0) {int t = coin[i].b / m[i];k = (t < k) ? t : k;}}for (i = 0; i < n; i ++) {if (m[i] > 0) {coin[i].b -= m[i] * k;}}res += k;//break;}printf("%d\n", res);return 0; }

POJ1862

Stripies

題意

科學家發現一種奇怪的玩意，他們有重量weight，如果他們碰在一起，總重變成2*sqrt(m1*m2)。要求出最終的重量的最小值。

思路

試一下就可以發現：對重量較大的先碰，可以對其多次sqrt，使得最后的結果最小。

代碼

Source CodeProblem: 1862 User: liangrx06 Memory: 220K Time: 16MS Language: C++ Result: Accepted Source Code #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std;const int N = 10000;int n; double a[N];void input() {cin >> n;for (int i = 0; i < n; i ++) {cin >> a[i];} }double coll(double x, double y) {return 2*sqrt(x*y); }double solve() {sort(a, a+n);for (int i = n-2; i >= 0; i --)a[i] = coll(a[i], a[i+1]);return a[0]; }int main(void) {input();double res = solve();printf("%.3lf\n", res);return 0; }

POJ3262

Protecting the Flowers

題意

有n個牛在FJ的花園亂吃。
所以FJ要趕他們回牛棚。
每個牛在被趕走之前每秒吃Di個花朵。趕它回去FJ來回要花的總時間是Ti×2。在被趕走的過程中，被趕走的牛就不能亂吃。

思路

貪心策略，對牛進行排序，排序的標準是，假設牛A與牛B要選一頭趕走，我們首先要選擇破壞最大的一頭牛趕走，留破壞小的牛。他們的破壞著呢麼計算呢？假設先趕走牛A，那么牛B造成的損失是2×TA×DB，先趕走牛B，那么牛A造成的損失是2×TA×DB，所以，只要判斷TA×DB與TA×DB誰大，就知道該先趕走誰了，所以數組排序的標準就是—Ti×Dj>Tj×Di。

代碼

Source CodeProblem: 3262 User: liangrx06 Memory: 1780K Time: 141MS Language: C++ Result: Accepted Source Code #include <iostream> #include <cstdio> #include <algorithm> using namespace std;const int N = 100000;struct Cow {int t, d;double v; };int n; Cow cow[N];void input() {cin >> n;for (int i = 0; i < n; i ++) {scanf("%d%d", &cow[i].t, &cow[i].d);cow[i].v = (double)(cow[i].d)/(double)(cow[i].t);} }bool cmp(const Cow &x, const Cow &y) {return x.v > y.v; }void solve() {sort(cow, cow+n, cmp);long long res = 0;int time = 0;res += time * cow[0].d;for (int i = 1; i < n; i ++) {time += 2*cow[i-1].t;res += time * cow[i].d;}printf("%lld\n", res); }int main(void) {input();solve();return 0; }

轉載于:https://www.cnblogs.com/liangrx06/p/5083767.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的《挑战程序设计竞赛》2.2 贪心法-其它 POJ3617 3069 3253 2393 1017 3040 1862 3262的全部內容，希望文章能夠幫你解決所遇到的問題。

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