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

            

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

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

  1. An Easy Problem poj2453
    //贪心, 将最右边第一个01改成10并将其右边的1都往右移到最低位
    
    #include
    
    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;
    }
  2. 最大子矩阵 openjudge1768

  3. 金银岛 openjudge1797

    //金属可分割, 所以直接贪心单位价值最大的优先选
    
    #include
    
    #include
    
    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;
    }
  4. 装箱问题 openjudge19

  5. Ride to Office openjudge2404

  6. 书架 openjudge2407

  7. 电池的寿命 openjudge2469

  8. 寻找平面上的极大点 openjudge2704

  9. 最小新整数 openjudge3528

  10. Crossing River openjudge702

  11. 接水问题 openjudge15

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像