POJ 3614
題目：http://poj.org/problem?id=3614
題意：c頭牛曬太陽，是以要塗防曬霜，第i頭牛需要 minSPF 和 maxSPF 機關強度之間的防曬霜，防曬霜有l種，第i種是SPF 機關強度的防曬，并且可以塗cover次，求最多可以滿足多少頭牛曬太陽。
解析：
因為題中有minspf和maxspf兩個變量需要考慮，是以考慮對其中一個排序來減少需要考慮的變量，此處選擇對minspf升序排序。
周遊方向有兩個，一個是從小到大，一個是從大到小。
應該是從大到小周遊，然後每次取能取中盡可能大的。對于該防曬，假如不被這頭牛取走而被另外的牛取走，因為它是能取的裡面最大的，是以所有小于它的符合條件的防曬也都符合這頭牛和另外那頭牛取走的條件，此時無法産生更優的選擇（更優的選擇指的是不被這頭牛取走，而這頭牛可以去得到另外那頭牛取不到的防曬，這樣就會産生更優解）
代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 3000;
struct node {
int l, r;
}num[maxn];
int val[maxn];
bool cmp(node a,node b) {
return a.l > b.l;
}
int main() {
int n, m; cin >> n >> m;
memset(val, 0, sizeof(val));
for (int i = 1; i <= n; i++) scanf("%d %d", &num[i].l, &num[i].r);
for (int i = 1; i <= m; i++) {
int inp1,inp2; scanf("%d %d", &inp1,&inp2);
//scanf("%d", &val[inp]);
val[inp1] += inp2;
}
sort(num + 1, num + n + 1, cmp);
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = num[i].r; j >= num[i].l; j--) {
if (val[j]) {
val[j]--;
cnt++;
break;
}
}
}
cout << cnt;
return 0;
}
POJ 3190
題目：http://poj.org/problem?id=3190
題意：
這裡有N隻 (1 <= N <= 50,000) 挑剔的奶牛! 他們如此挑剔以緻于必須在[A,B ]的時間内産奶(1 <= A <= B <= 1,000,000)當然, FJ必須為他們創造一個決定擠奶時間的系統.當然，沒有牛想與其他奶牛分享這一時光
幫助FJ做以下事:
- 使每隻牛都有專屬時間的最小牛棚數
- 每隻牛在哪個牛棚
也許有很多可行解。輸出一種即可，采用SPJ （翻譯來自vjudge）
題解：
我看到這道題第一思路就是逐個逐個牛棚，先将每一頭牛按照産奶時間A 從小到大排序，A一樣再按B從小到大排，接着從第一頭牛開始判斷，往下周遊，遇到某頭牛的A比第一頭牛的B要大就更新，然後标記改牛。然後再從頭開始選擇第二個牛棚。為了減少時間複雜度，周遊的時候可以采用倍增的思想，但是時間複雜度還是很高。
本題可以使用優先隊列，優先隊列按照結束時間升序排列，對于牛的初始化是按照上面的方法一樣，然後隻需要周遊一次，每次取堆頂，假如堆頂結束時間小于該點開始時間，那麼pop，再push新的這點，否則直接push。
代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 5e4 + 9;
struct node {
int l, r, ind;
}num[maxn];
bool cmp(node a, node b) {
if (a.l < b.l) return 1;
else if (a.l == b.l) return a.r < b.r;
else return 0; //!!
}
typedef pair<int,int> P;
priority_queue<P, vector<P>, greater<P>> Q;
int flag[maxn];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) scanf("%d %d", &num[i].l, &num[i].r), num[i].ind = i;
sort(num + 1, num + 1 + n, cmp);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (Q.empty()) {
cnt++;
Q.push(P(num[i].r, cnt));
flag[num[i].ind] = cnt;
continue;
}
P p = Q.top();
if (p.first < num[i].l) {
Q.push(P(num[i].r, p.second));
Q.pop();
flag[num[i].ind] = p.second;
}
else {
cnt++;
Q.push(P(num[i].r, cnt));
flag[num[i].ind] = cnt;
}
}
cout << cnt << endl;
for (int i = 1; i <= n; i++) {
printf("%d\n", flag[i]);
}
return 0;
}
POJ 1328
題目：http://poj.org/problem?id=1328
解法：
二維化一維嘛，很正常的思路，求出每個點可以檢測到的雷達可以放置的範圍，然後将問題轉化為一維區間放置最少的點使得區間能被點覆寫，将區間按照結束排序，具體看代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e3 + 7;
struct node {
double l, r;
}num[maxn];
inline bool cmp(node a, node b) {//按結束時間排序
return a.r < b.r;
}
int main() {
int n, d;
int cnt = 0;
while (scanf("%d %d", &n, &d), n) {
cnt++;
int ok = 1;
if (d <= 0) ok = 0;
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d %d", &a, &b);
double flag = 1.0*d*d - 1.0*b*b;
if (flag < 0) {
ok = 0;
continue;
}
flag = sqrt(flag);
num[i].l = a - flag;
num[i].r = a + flag;
}
if (!ok) {
cout << "Case " << cnt << ": " << -1 << endl;
continue;
}
sort(num + 1, num + 1 + n, cmp);
int ans = 0;
double las_x = -1000000.0;
for (int i = 1; i <= n; i++) {
if (num[i].l > las_x) {
ans++;
las_x = num[i].r;
}
}
cout << "Case " << cnt << ": " << ans << endl;
}
return 0;
}
POJ 2054 Color a Tree
http://poj.org/problem?id=2054
題意： 給一棵樹染色，對某一個點染色的時候，其父節點必須被染色，一開始染根節點。
輸入：
第一行兩個數：節點數n，根節點r
第二行n個數，每個根節點的價值vi
第三行~最後，每行兩個數：父節點，節點
染色代價=已經染了的點的數目*節點的價值。
這道題貪心我想不出來，我能想出來的是遞歸，就是染了根節點之後其子節點可以看成另外全新的樹，但是不曉得怎麼寫。
貪心的做法是：
樹的節點裡面最大的那個點，假如可以染，一定會優先染。那麼染那個點的條件是染它的父節點，也就是說染父節點+染最大的那個點這個操作是綁定的，是以我們可以将這兩個點合并。合并後變成一個全新的點，該點的價值=點的總價值/點由幾個點組成。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e3 + 7;
int n, r;
int Rank[maxn]; // Rank 記錄的是染色路徑，rank【i】=j --- 先i在j
struct node {
int fat, c ,crow; //fat : 父節點 c：價值 crow：這個點由幾個點組成
double val,total; //val，total ： 因為需要取平均值，是以這兩個用于比較用途
}num[maxn];
int trace(int nod) { // 找出一個大點裡面最後被染色的點
return Rank[nod] == -1 ? nod : trace(Rank[nod]);
}
int main() {
while (scanf("%d %d", &n, &r), n&&r) {
memset(Rank, -1, sizeof(Rank));
//輸入
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i].c);
num[i].val = num[i].c*1.0;
num[i].total = num[i].val;
num[i].crow = 1;
}
for (int i = 2; i <= n; i++) {
int fro, to; scanf("%d %d", &fro, &to);
num[to].fat = fro;
}
num[r].fat = 0;
while (1) {
double maxx = -1;
int maxx_i;
for (int i = 1; i <= n; i++) { //找出權值最大的點
if (num[i].val > maxx &&i != r) maxx_i = i, maxx = num[i].val;
}
if (maxx == -1) break; //找不到就退出
int fat = num[maxx_i].fat;
num[fat].total += num[maxx_i].total; //合并點 ， 處理權值
num[fat].crow += num[maxx_i].crow;
num[fat].val = num[fat].total / num[fat].crow;
num[maxx_i].val = -1;
for (int i = 1; i <= n; i++) { //合并點，處理節點連結問題，這裡采取向根部方向合并
if (num[i].fat == maxx_i) num[i].fat = fat;
}
Rank[trace(fat)] = maxx_i; //記錄
}
int sum = 0, day = 1, ind = r;
while (ind!=-1) {
sum += day++ * num[ind].c;
ind = Rank[ind];
}
cout << sum << endl;
}
return 0;
}
![CF1394C 計算幾何[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)