題目要求：
奶牛的卡車壞了，需要到小鎮(zhèn)修理∑固桑現(xiàn)在有油P個單位招盲，距小鎮(zhèn)L個單位，每走一單位嘉冒，油少一單位曹货。途徑N個補給站咆繁，補給站分別給出到小鎮(zhèn)的距離和能加油的數(shù)量。求問為了到達小鎮(zhèn)最少加油次數(shù)顶籽。
思路：
1玩般、首先把數(shù)據(jù)存儲在二維數(shù)組中，a[i][0]表示第i個補給站到小鎮(zhèn)的距離礼饱，a[i][1]表示第i個補給站存儲油量坏为。最后一個元素存儲L和P。
2镊绪、因為只有一條到達小鎮(zhèn)的路匀伏，因此選擇目前能到的存儲油量最大的補給站為最優(yōu)。將補給站按照a[i][0]降序排序镰吆，則如果遇到目前油量到達不了的補給站帘撰，直接break，因為之后的更不能到達万皿。記錄a[i][1]字段的最大值和取最大值時的位置摧找。
3、最終最大值為本次選取的補給站牢硅，將其油量置為0蹬耘，不再被選擇，將油量加入a[n][1]减余，再次比較a[n][1]和a[n][0]综苔，如果a[n][1]>=a[n][0]如果所有可到達的補給站都油量為0，則位置為-1位岔，表示失敗如筛，小鎮(zhèn)無法到達。
//
// main.cpp
// eoj1855
//
// Created by Haoying Zhao on 17/7/20.
// Copyright ? 2017年 Haoying Zhao. All rights reserved.
//
#include <iostream>
using namespace std;
int a[10001][2];
int cmp(const void* a, const void* b) {
return ((int *)b)[0]-((int *)a)[0];
}
int find_max(int n) {
int max = 0, pos = -1;
for(int i = 0; i < n; i++) {
if(a[n][1] + a[i][0] < a[n][0])
break;
if(max < a[i][1]) {
max = a[i][1];
pos = i;
}
}
if(pos != -1) {
a[n][1] += max;
a[pos][1] = 0;
}
return pos;
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i][0];
cin >> a[i][1];
}
cin >> a[n][0];
cin >> a[n][1];
int count = 0;
qsort(a, n, sizeof(a[0]), cmp);
while(a[n][1] < a[n][0]) {
if(find_max(n) == -1) {
count = -1;
break;
}
else count ++;
}
cout << count << endl;
return 0;
}
總結(jié)：
- 要對補給站排序減少運算次數(shù)否則超時抒抬。
- qsort對二維數(shù)組排序：
int cmp(const void* a, const void* b) {
return ((int *)b)[0]-((int *)a)[0];
}
int main() {
int a[3][2];
a[0][0] = 1;
a[1][0] = 3;
a[2][0] = 2;
a[0][1] = 4;
a[1][1] = 5;
a[2][1] = 6;
qsort(a, 3, sizeof(a[0]), cmp);
for(int i = 0; i < 3; i++) {
cout << "i = " << i << ": "<< a[i][0] << " " << a[i][1] << endl;
}
return 0;
}
