头像

AnrolsP




离线:2天前


活动打卡代码 AcWing 1227. 分巧克力

AnrolsP
1个月前
//通过二分来求解,给定一个长度x, sum((Hi / x) * (Wi / x)) 就是巧克力块数
//当sum <= k 代表,x要减小,范围缩小为[L, x]
//当sum > k , x增大, 范围扩大为[x + 1, R]
//此时x 是整数,因此是整数二分
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int N = 100010;
int q[N], w[N], h[N];
int n, k;

bool check(int x)
{
    int sum = 0;
    for (int i = 0; i < n; i ++)
    {
        sum += (h[i] / x) * (w[i] / x);
    }
    return sum > k;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n ; i++)
    {
        scanf("%d%d", & h[i], &w[i]);
    }
    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r>> 1;
        if (check(mid)) l = mid + 1;
        else r = mid;
    }
    cout << r - 1 << endl;
    return 0;
}


活动打卡代码 AcWing 1353. 滑雪场设计

AnrolsP
1个月前
//证明1:最优解的山峰的高度范围都是[0, 100] 
//由于最高峰和最低峰的高度差不超过17,因此一共有84个区间[0, 17], [1, 18]……,[84, 100]
//因此枚举每个区间,计算把山峰都修改到区间高需要的花费,求出最小花费

#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
const int N = 1010;
int q[N];

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n ;i ++)
        scanf("%d", &q[i]);
    int res = 0x3f3f3f3f;
    for (int i = 0; i + 17 < 100; i ++)
    {
        int cost = 0, l = i, r = i + 17;
        for (int j = 0; j < n; j ++)
        {
            if (q[j] < l) cost += (l - q[j]) * (l - q[j]);
            else if (q[j] > r) cost += pow(q[j] - r, 2);
        }
        res = min(res, cost);
    }
    cout << res << endl;
    return 0;
}




活动打卡代码 AcWing 420. 火星人

AnrolsP
1个月前

//从后向前找,找到第一个不是降序排列的点k 有a[k] < a[k + 1], a[k + 1]后面就是降序序列
//把a[k] 和 降序序列中略大于a[k]的 a[j]交换,再把更新的降序序列颠倒
//这样的序列就是略大于原序列的排列

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
const int N = 10010;
int q[N];


int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++)
        scanf("%d", &q[i]);
    while (m--)
    {
        int k = n - 2;
        while (q[k] > q[k + 1])k--;
        int t = k + 1;
        //找降序序列中稍微比q[k]大的数
        while (t + 1 < n && q[t + 1] > q[k])t++;
        //cout << k << " " << t << endl;
        swap(q[t], q[k]);
        reverse(q + k + 1, q + n);

    }
    for (int i = 0; i < n; i ++)
        printf("%d ", q[i]);
    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

AnrolsP
1个月前

//从后向前找,找到第一个不是降序排列的点k 有a[k] < a[k + 1], a[k + 1]后面就是降序序列
//把a[k] 和 降序序列中略大于a[k]的 a[j]交换,再把更新的降序序列颠倒
//这样的序列就是略大于原序列的排列

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
const int N = 10010;
int q[N];


int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++)
        scanf("%d", &q[i]);
    while (m--)
    {
        int k = n - 2;
        while (q[k] > q[k + 1])k--;
        int t = k + 1;
        //找降序序列中稍微比q[k]大的数
        while (t + 1 < n && q[t + 1] > q[k])t++;
        //cout << k << " " << t << endl;
        swap(q[t], q[k]);
        reverse(q + k + 1, q + n);

    }
    for (int i = 0; i < n; i ++)
        printf("%d ", q[i]);
    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

AnrolsP
1个月前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int f[N], a[N], g[N];


int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    for(int i = 1; i <= n; ++i)
    {
        f[i] = 1;
        for(int j = 1; j < i; ++j)
        {
            if(a[j] < a[i])f[i] = max(f[i], f[j] + 1);
        }
    }
    for(int i = n; i >= 1;--i)
    {
        g[i] = 1;
        for(int j = n; j > i; --j)
            if(a[j] < a[i])g[i] = max(g[i], g[j] + 1);
    }
    //cout << f[n] << " " << g[1] <<endl;
    int res = 0;
    for(int k = 1; k <= n; ++k)
    {
        res = max(res, f[k] + g[k] - 1);
    }
    cout << n - res <<endl;
    return 0;
}


活动打卡代码 AcWing 1603. 整数集合划分

AnrolsP
1个月前
//其实我们只要让两个集合中的数个数最相近,并且起一个集合中的数都比第二个集合中的数小,这样差就是尽可能的大
//把所有的数排序,前 [n / 2] 就是属于第一个集合


#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1e5 + 10;
int n;
int w[N];

void quicksort(int l, int r)
{

    if (l >= r)return ;
    int mid = l + r >> 1;
    int t = w[mid];
    int i , j;
    for ( i = l - 1, j = r + 1; i < j;)
    {
        do i++; while(w[i] < t);
        do j--; while(w[j] > t);
        if (i < j) swap(w[i], w[j]);
    }
    quicksort(l, j);
    quicksort(j + 1, r);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        scanf("%d", &w[i]);
    quicksort(0, n -  1);
    //计算差
    int res = 0;
    if (n % 2 == 0)
    {
        for (int i = 0; i < n / 2; i ++)
            res += w[n / 2 + i] - w[i];
        cout << 0 << " " <<  res << endl;
    }
    else
    {
        for (int i = 0; i < n / 2; i ++)
        {
            res += w[n / 2 + i] - w[i];
        }
        res += w[n - 1];

        cout << 1 << " " <<  res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

AnrolsP
1个月前
//从N条绳子中切出M条绳子
/*
把最优解的问题转换成判定类问题:
求裁剪后的最大长度 -> 给定一个长度x,求裁出这个长度的绳子数量,裁剪出的绳子数量就是sum(Li / x)
总区间是[L, R]
此时有两种情况:
sum(Li / x) < m :那么答案在的区间就是[L, x]
sum(Li / x) >= m : 那么答案在的区间就是[x, R]
这符合二分的思想,x就是要查找的数,x是小数,因此判断大小使用 y-x < 1e^-(k + 2)(k是保留位数) 的标准
浮点数二分
*/

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N= 1e6 + 10;
int w[N];
int n, m;

bool check(double mid)
{
    int sum = 0;
    for (int i = 0; i < n ; i ++ )
    {
        sum += w[i] / mid;
    }
    return sum < m;
}

int main()
{
    cin >> n >> m;
    for (int i = 0 ; i < n ; i ++)
        cin >> w[i];
    double l = 0, r = 1e9;

    while (r - l > 1e-4)
    {
        double mid =(l + r) / 2;
       //cout << mid << endl;
        if (check(mid)) r = mid;
        else l = mid;
    }
    printf("%.2lf", l);
    return 0;
}



活动打卡代码 AcWing 1346. 回文平方

AnrolsP
1个月前
//如何将一个数转换成b进制
//使用除余法,转换成b进制,再使用双指针法判断是否是回文数
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

//"" + 1不能显示出ascII码
string  get(int num)
{
    string snum;
    if (num <= 9)
        snum = num + '0';
    else snum =  num - 10 + 'A';
   // cout <<snum << endl;
    return snum;
}

bool check(string num)
{
    for (int i = 0, j = num.size() - 1; i < j; i ++, j --)
    {
        if (num[i] != num[j]) return false;
    }
    return true;
}

string parse(int num, int base)
{
    string snum;
    while(num)
    {
        snum += get(num % base);
        num /= base;
    }
    reverse(snum.begin(), snum.end());
    return snum;
}

int main()
{
    int b; cin >> b;
    for (int i = 1; i <= 300; i ++ )
    {
        string num = parse(i * i, b);
        //cout <<num << endl;
        if (check(num))
        {
            cout <<parse(i, b) <<" " << num  << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

AnrolsP
1个月前
#include<iostream>
#include<queue>
using namespace std;
const int N = 25;

#define x first
#define y second

typedef pair<int, int> PII;
int n, m;
char f[N][N];
PII q[N];
int bfs(int x, int y)
{
    int res = 1;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    int hh = 0, tt = -1;
    q[++ tt] = {x, y};
    f[x][y] = '#';
    while (hh <= tt)
    {
        PII t = q[hh ++];
        for (int i = 0; i < 4; i ++)
        {
            int nx = dx[i] + t.x, ny = dy[i] + t.y;
            if  (nx < 0 || nx >= n || ny < 0 || ny >= m || f[nx][ny] == '#') continue ;
            res ++;
            q[++ tt] = {nx, ny};
            f[nx][ny] = '#';
            //cout << t.x << " " << t.y << " " << " " << res << endl;
        }
    }
    return res;
}

int main()
{
    int x = 0, y = 0;
    while (cin >> m >> n, n || m)
    {
        for (int i = 0; i < n; i ++)
            cin >> f[i];
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j++)
                if (f[i][j] == '@')
                {
                   x = i; y = j;
                }
        cout << bfs(x, y) << endl;
    }


    return 0;
}


活动打卡代码 AcWing 756. 蛇形矩阵

AnrolsP
1个月前
#include<iostream>
using namespace std;
const int N = 110;
int n, m;
int q[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
    cin >> n >> m;
    int x = 0, y = 0;
    int d = 0;
    for (int i = 1; i <= n * m; i ++)
    {
        q[x][y] = i;
        int nx = dx[d] + x, ny = dy[d] + y;
        if (nx >= n || nx < 0 || ny >= m || ny < 0 || q[nx][ny])
        {
            d = (d + 1) % 4;
            nx = dx[d] + x; ny = dy[d] + y;

        }
        x= nx; y = ny;
    }
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
            printf("%d ", q[i][j]);
        puts("");
    }
    return 0;
}