C++奥赛一本通贪心题解

C++奥赛一本通刷题记录(贪心)

2017.11.15 By gwj1139177410
书不见了，占坑待填。

1. An Easy Problem poj2453

//贪心, 将最右边第一个01改成10并将其右边的1都往右移到最低位
#include<iostream>
using namespace std;
int main(){
    unsigned int n, x;
    while(cin>>n &&n){
        x = n&-n;
        cout<<(n+x+(n^(n+x))/x/4)<<"\n";//感受一下来自位运算的恐惧吧
    }
    return 0;
}

1. 最大子矩阵 openjudge1768
2. 金银岛 openjudge1797

//金属可分割, 所以直接贪心单位价值最大的优先选
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 10010;
int w, s;  double ans;
struct node{ double n, v; }a[maxn];
bool cmp(node a, node b){ return a.v/a.n>b.v/b.n;}
int main(){
    int T;  scanf("%d", &T);
    while(T--){
        ans = 0;
        scanf("%d%d", &w,&s);
        for(int i = 1; i <= s; i++)
            scanf("%lf%lf", &a[i].n, &a[i].v);
        sort(a+1,a+s+1,cmp);
        for(int i = 1; i<=s; i++){
            if(w >= a[i].n){ w -= a[i].n; ans += a[i].v; }
            else { ans += a[i].v/a[i].n*w; break; }
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}

1. 装箱问题 openjudge19
2. Ride to Office openjudge2404
3. 书架 openjudge2407
4. 电池的寿命 openjudge2469
5. 寻找平面上的极大点 openjudge2704
6. 最小新整数 openjudge3528
7. Crossing River openjudge702
8. 接水问题 openjudge15