头像

菜鸡一个

Acwing


访客:3065

离线:19天前


活动打卡代码 AcWing 567. 硬币

菜鸡一个
3个月前

思路

简单的思维题
如果 m <= n 只需要 1
如果 m > n 而且 m % n == 0 只需要 m / n
否则 m / n + 1

代码

#include <iostream>

using namespace std;


int main() 
{
    int n, m;
    cin >> n >> m;
    if(n >= m) 
        cout << 1 << endl;
    else 
        if(m % n == 0) 
            cout << m / n << endl;
        else
            cout << ( m / n + 1) << endl;

    return 0;
}



菜鸡一个
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int  N = 100010;

struct Range
{
    int l;
    int r;
}p[N];

bool cmp(const Range &a,const Range &b)
{
    return a.r < b.r;
}

int n;
int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    scanf("%d%d",&p[i].l,&p[i].r);

    sort(p,p+n,cmp);

    int res=0,end=-2e9;
    for(int i=0;i<n;i++)
    {
        if(p[i].l>end)
        {
            res++;
            end=p[i].r;
        }
    }

    printf("%d\n",res);

    return 0;
}



菜鸡一个
10个月前

思路:

  1. 将每个区间按右端点从小到大排序
  2. 从前往后依次枚举每个区间,如果当前区间中已经包含,则pass
    否则,选择当前区间的右端点

结构体排序

struct Range
{
    int l;
    int r;
}p[N];

bool cmp(const Range &a, const Range &b)
{
    return a.r<b.r;
}

枚举每个区间

int res=0,end=-2e9;
for(int i=0;i<n;i++)
{
    if(p[i].l>end)
    {
        res++;
        end=p[i].r;
    }
}

Ac代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 100010;
struct Range
{
    int l, r;
}p[N];

bool cmp(const Range &a, const Range &b)
{
    return a.r < b.r;
}
int n;

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&p[i].l,&p[i].r);
    }
    sort(p, p+n, cmp);

    int res = 0,end = -2e9;
    for(int i=0;i<n;i++)
    {
        if(p[i].l>end)
        {
            end=p[i].r;
            res++;
        }
    }
    printf("%d\n",res);

    return 0;
}


活动打卡代码 AcWing 905. 区间选点

菜鸡一个
10个月前

思路:

  1. 将每个区间按右端点从小到大排序
  2. 从前往后依次枚举每个区间,如果当前区间中已经包含,则pass
    否则,选择当前区间的右端点

结构体排序

struct Range
{
    int l;
    int r;
}p[N];

bool cmp(const Range &a, const Range &b)
{
    return a.r<b.r;
}

枚举每个区间

int res=0,end=-2e9;
for(int i=0;i<n;i++)
{
    if(p[i].l>end)
    {
        res++;
        end=p[i].r;
    }
}

Ac代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 100010;
struct Range
{
    int l, r;
}p[N];

bool cmp(const Range &a, const Range &b)
{
    return a.r < b.r;
}
int n;

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&p[i].l,&p[i].r);
    }
    sort(p, p+n, cmp);

    int res = 0,end = -2e9;
    for(int i=0;i<n;i++)
    {
        if(p[i].l>end)
        {
            end=p[i].r;
            res++;
        }
    }
    printf("%d\n",res);

    return 0;
}


活动打卡代码 AcWing 53. 最小的k个数

菜鸡一个
10个月前

容器内怎么用sort排序

    sort(res.begin(),sort.end())
    class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        int n = input.size();
        sort(input.begin(), input.end());
        vector<int> res;
        for(int i = 0 ;i < k; i ++)
        res.push_back(input[i]);

        return res;
    }
};



菜鸡一个
10个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

STL的基本用法

  1. vector[HTML_REMOVED] array
  2. array.push_back()
  3. res.rbegin, res.rend
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        while(head)
        {
            res.push_back(head -> val);
            head = head -> next;
        }

        return vector<int> (res.rbegin(), res.rend());
    }
};



菜鸡一个
10个月前

双指针算法

class Solution {
public:
    void reOrderArray(vector<int> &array) {


         int l = 0, r = array.size() - 1;
         while(l < r)
         {
             while(l < r&&array[l] % 2 == 1) l ++;
             while(l < r&&array[r] % 2 == 0) r --;

             if(l < r) swap(array[l], array[r]);
         }
    }
};



菜鸡一个
10个月前

二分问题

  1. 最大值最小
    ‘’‘
    mid = l + r >> 1
    r = mid;
    l = mid + 1
    ‘’‘
  2. 最小值最大
    ‘’‘
    mid = (l + r + 1) / 2;
    l = mid
    r = mid - 1
class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;

        while(l < r)
        {
            int mid = (l + r) >> 1;

            if(nums[mid] != mid)
            r = mid;
            else 
            l = mid + 1;
        }

        if(nums[r] == r)
        r ++;

        return r;

    }
};



菜鸡一个
10个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int ans = 0;
        for(int i = 0;i < nums.size(); i ++)
        if(nums[i] == k)
        ans ++;

        return ans;
    }
};


活动打卡代码 AcWing 869. 试除法求约数

菜鸡一个
11个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
int app[1000000],cnt;
void divide(int x)
{
    memset(app,0,sizeof(app));
    cnt=0;
    for(int i=1;i<=x/i;i++)
    {
        if(x%i==0)
        {
            app[cnt++]=i;
            if(i*i!=x)
            app[cnt++]=x/i;
        }
    }
    sort(app,app+cnt);
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        divide(x);
        for(int i=0;i<cnt;i++)
        cout<<app[i]<<" ";
        cout<<endl;
    }

    return 0;
}