題目連接；10026 Shoemaker's Problem

題目大意：有一個(gè)鞋匠接了n雙要修的鞋子， 修每雙鞋需要d天，每推遲一天修將虧損val元，問按什么樣的順序修鞋可以保證損失最少，如果有多種情況輸出字典序最小的。

解題思路：最開始把損失錢數(shù)最大的放在前面，后來發(fā)現(xiàn)每層子問題是相互有影響的，所以不能從整體的損失來看，所以后來改成對(duì)兩個(gè)鞋的裝態(tài)比較，只要考慮哪雙鞋放前和哪雙鞋放后就可以了。

?

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1005;struct State {int id;int day;int val; }num[N];bool cmp(const State &a, const State &b) {return a.val * b.day > b.val * a.day; }int main() {int cas, n;scanf("%d", &cas);while (cas--) {scanf("%d", &n);for (int i = 0; i < n; i++) {num[i].id = i + 1;scanf("%d%d", &num[i].day, &num[i].val);}sort(num, num + n, cmp);for (int i = 0; i < n - 1; i++)printf("%d ", num[i].id);printf("%d\n", num[n -1].id);if (cas)printf("\n");}return 0; }

?

?

總結(jié)

以上是生活随笔為你收集整理的uva 10026 Shoemaker's Problem(排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。