算法练习1

一时失言乱红尘 2021-12-02 00:58 320阅读 0赞

小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力

##### **输入描述:** #####

每个输入包含一个测试用例。
    每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。

##### **输出描述:** #####

输出一个数表示小Q第一天最多能吃多少块巧克力。

示例1

## 输入 ##

3 7

## 输出 ##

#include <iostream>
    using namespace std ;
    
    //本体使用二分查找的思想，不断分半查找
    //计算按照当前这种分法巧克力数量够不够
    int calSum(int mid, int days) {
        
        
        int sum = 0 ;
        //向上取整
        for(int i=0; i<days; i++) {
        
            sum += mid ;
            mid = (mid%2==0)?(mid/2):(mid/2+1);
        }
        return sum ;
    }
    
    
    int solve(int& cNum, int& days) {
        
        int first, last, mid, total  ;
        first = 0 ;
        total = cNum ;
        last = cNum ;
        //巧克力的数量连天数都不够
        if(cNum < days) {
        
            return -1 ;
        } 
        //和天数相等的话，每天吃一片
        if(cNum == days) {
        
            return 1 ;
        }
        int s = first+last ;
        //巧克力的数目为偶数，折半；为奇数，向上取整
        mid = (s%2==0)? s/2:(s/2+1) ;
        //查找的左边界要小于右边界
        while(first < last) {
        
            int sum = calSum(mid, days) ;       
            
            if(sum < total) {
        
                first = mid;
            }
            else if(sum == total) {
        
                return mid ;
            }
            else {
        
                last = mid-1 ;
            }
    
            int s = first+last ;
            mid = (s%2==0)? s/2:(s/2+1) ;
        }
        return mid ;
    }   
    
    int main()
    {
        
        int cNum, days ;
        //输入巧克力的数量和天数
        cin >> days >> cNum;
        int num = solve(cNum, days) ;
        cout << num << endl ;
        return 0;
    }

牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。  
牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。  
他们的得分等于他们抽到的纸牌数字总和。  
现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。

##### **输入描述:** #####

输入包括两行。
    第一行包括一个正整数n(1 <= n <= 105)

,表示纸牌的数量。  
第二行包括n个正整数ai(1 <= a i <= 109),表示每张纸牌上的数字。

##### **输出描述:** #####

输出一个整数, 表示游戏结束后牛牛得分减去羊羊得分等于多少。

示例1

## 输入 ##

3
    2 7 4

## 输出 ##

1.最优策略。所谓最优就是当轮到自己抽牌时，直接选择最大的牌。这样每当两个人都抽完了牌之后，用牛牛的牌面值减去羊羊的牌面值，就是差值的一部分。然后这样一直计算到第一个数。最后将所有的差值都加起来就得到了解。  
2.还要考虑一个牌的数量的奇偶问题。如果牌数量为偶数，则将n/2个差值加起来；若牌数量为奇数，那么牌面值最小的牌直接给了牛牛，这个值要加到差值的总和里。

#include <iostream>
    #include<vector>
    #include<algorithm>
    using namespace std ;
    
    int main()
    {
        
        //纸牌数组
        int n = 0 ;
        cin >> n ;
        vector<int> arr ;
        for(int i=0; i<n; i++) {
        
            int m ;
            cin >> m ;
            arr.push_back(m) ;
        }   
        int sum = 0 ;
        //给数组从大到小排序
        sort(arr.rbegin(), arr.rend()) ;
        
        int niu , yang;
        int flag = 0 ;
        for(int i=0; i<n ;i+=2) {
        	
    	//轮到最后一个值了，判断纸牌数目要是奇数的话，将最后一个纸牌直接加入到sum中
            flag = 0 ;
            niu = arr[i]  ;
            if(i+1<n) {
        
    			//本次羊羊能获取到纸牌
                flag = 1 ;
                yang = arr[i+1] ;
            }
            //用牛的纸牌减去羊的牌
            if(flag == 1)
            sum += niu - yang ;
        }
        
        if(n%2 == 1) {
        
            sum+=niu ;
        }
        cout <<  sum << endl ;
        return 0;
    }