友塔-3-17码上offer

一星

给定一个 m，求一个 m = 2^a + 2^b 的 a 和 b 是否存在，存在正序输出，不存在则输出-1

// 100%， 这道题没记录，只能靠记忆，可能有差错
int main()
{
    int m;
    while ( cin >> m )
    {
        if ( m == 0 || m == 1 )
        {
            cout << "-1" << endl;
            continue;
        }
        int a = log2(m);
        if ( m == pow(2, a) )
        {
            cout << a - 1 << " " << a - 1 << endl;
        }
        else
        {
            int b = log2(m - pow(2, a));
            if ( m - pow(2, a) == pow(2, b) )
            {
                cout << min(a, b) << " " << max(a, b) << endl;
            }
            else
            {
                cout << "-1" << endl;
            }
        }
    }
}

二星

数组排序，每次只能用0和其他排

bool IsSort(const vector<int> vec)
{
    for ( auto i = 0; i < vec.size(); ++i )
    {
        if ( i != vec[i] )
            return false;
    }
    return true;
}

vector<int> NotSortNum(const vector<int> vec)
{
    vector<int>res;
    for ( auto i = 0; i < vec.size(); ++i )
    {
        if ( i != vec[i] )
        {
            res.push_back(vec[i]);
        }
    }
    return res;
}
int main()
{
    long long n;
    while ( cin >> n )
    {
        vector<int>numVec(n);
        map<int, int>numMap;
        for ( auto i = 0; i < n; ++i )
        {
            cin >> numVec[i];
            numMap[numVec[i]] = i;
        }
        int count = 0;
        while ( !IsSort(numVec) )
        {
            auto noSort = NotSortNum(numVec);
            if ( numMap[0] == 0 && !noSort.empty() )
            {
                auto secondPos = numMap[noSort[0]];
                swap(numVec[0], numVec[secondPos]);
                numMap[0] = secondPos;
                numMap[noSort[0]] = 0;
                ++count;
            }
            if ( numMap[0] != 0 && !noSort.empty() )
            {
                auto zeroPos = numMap[0];
                auto secondPos = numMap[numMap[0]];
                swap(numVec[zeroPos], numVec[secondPos]);
                numMap[numMap[0]] = zeroPos;
                numMap[0] = secondPos;
                ++count;
            }
        }
        cout << count << endl;
    }
}

求最大能做的价值数

// 100%
int CanDo(vector<int>& dayVec, int day)
{
    for ( auto i = day; i > 0; --i )
    {
        if ( dayVec[i] != 0 )
        {
            return i;
        }
    }
    return -1;
}
int main()
{
    int n;
    while ( cin >> n )
    {
        int sum = 0;
        vector<pair<int, int>> numVec(n);
        vector<int> dayVec = { 0,0,0,0,0,0,0,0,1,1,0,
            1,1,1,1,1,1,0,1,1,1,
            1,1,0,0,1,1,1,1,1,1,0 };

        for ( auto i = 0; i < n; ++i )
        {
            cin >> numVec[i].first >> numVec[i].second;
        }
        sort(numVec.begin(), numVec.end(), [](auto a, auto b)->bool{return a.first > b.first; });
        for ( auto i : numVec )
        {
            int doDay = CanDo(dayVec, i.second);
            if ( doDay != -1 )
            {
                sum += i.first;
                dayVec[doDay] = 0;
            }
        }
        cout << sum << endl;
    }
}