头像

楚天

AFO大学见




离线:4天前



楚天
5天前

这道题是一道实数域进行二分的题目

比整数二分要好写,不用考虑边界死循环的问题

只要我们限定住我们的精确度就好了,(一个while循环搞定)

那么只要大力二分就好了

下面主要来说说check函数的部分

精髓就在check函数,即判断当前二分的答案是否合法的函数

依据题意,其实就是每次都让你的E在原来的基础上先乘2再减去你下一个要跳去的楼高(拿笔推一下就好)

每次做完这样一轮运算后,检查当前的E是否为负数

如果为负数直接return false

否则一直进行,直到进行n轮后还没退出,那么我们就返回true

最后用ceil函数向上取整并输出r即可

代码

#include<bits/stdc++.h>
using namespace std;
double h[200000];
int n;

bool check(double mid)
{
    for(int i=1;i<=n;i++)
    {
        mid=mid*2-h[i];
        if(mid<0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&h[i]);
    }
    double l=0;
    double r=1e8;
    while(r-l>0.00001)
    {
        double mid=(r+l)/2;
        if(check(mid))
        {
            r=mid;
        }
        else l=mid;
    }
    cout<<ceil(r)<<endl;
    return 0;
}




楚天
5天前
#include<bits/stdc++.h>
using namespace std;
double h[200000];
int n;

bool check(double mid)
{
    for(int i=1;i<=n;i++)
    {
        mid=mid*2-h[i];
        if(mid<0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&h[i]);
    }
    double l=0;
    double r=1e8;
    while(r-l>0.00001)
    {
        double mid=(r+l)/2;
        if(check(mid))
        {
            r=mid;
        }
        else l=mid;
    }
    cout<<ceil(r)<<endl;
    return 0;
}



活动打卡代码 AcWing 507. 积木大赛

楚天
10天前
#include<bits/stdc++.h>
using namespace std;
int a[200000];
int n;
long long ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        ans=ans+max(0,a[i+1]-a[i]);
    }
    ans+=a[1];
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 496. 机器翻译

楚天
11天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool st[2000];
queue<int> q;
int res;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(!st[x])
        {
            if(q.size()==m)
            {
                int t=q.front();
                q.pop();
                q.push(x);
                st[x]=1;
                st[t]=0;
                res++;
            }
            else
            {
                q.push(x);
                st[x]=1;
                res++;
            }
        }
    }
    cout<<res<<endl;
}


活动打卡代码 AcWing 148. 合并果子

楚天
11天前
#include<bits/stdc++.h>
using namespace std;
priority_queue< int ,vector<int> ,greater<int> > heap;
int n;
int res;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        heap.push(x);
    }
    while(heap.size()>1)
    {
        int x,y;
        x=heap.top();
        res+=heap.top();
        heap.pop();
        y=heap.top();
        res+=heap.top();
        heap.pop();
        heap.push(x+y);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 211. 计算系数

楚天
14天前
#include<iostream>
#include<cmath>

using namespace std;
const int mod=10007;
const int N=1010;
int a,b,k,n,m;
int c[N][N];
void init()
{
    for(int i=0;i<=1000;i++)
        for(int j=0;j<=i;j++)
        {
            if(j==0) c[i][j]=1;
            else    c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
}

int qmi(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=(long long)ans*a%mod;
        a=(long long)a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
int main()
{
    init();//预处理出组合数
    cin>>a>>b>>k>>n>>m;
    cout<<(long long)qmi(a,n)*qmi(b,m)*c[k][n]%mod;
    return 0;

}


活动打卡代码 AcWing 312. 乌龟棋

楚天
15天前
#include <bits/stdc++.h>
using namespace std;
const int M = 45;
int f[M][M][M][M];
int num[5];
int n, m;
int score[200000];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &score[i]);
    for (int i = 1; i <= m; i++)
    {
        int t;
        scanf("%d", &t);
        num[t]++;
    }
    for (int i = 0; i <= num[1]; i++)
    {
        for (int j = 0; j <= num[2]; j++)
        {
            for (int z = 0; z <= num[3]; z++)
            {
                for (int k = 0; k <= num[4]; k++)
                {
                    int so = score[i + j * 2 + z * 3 + k * 4 + 1];
                    if (i >= 1)
                    {
                        f[i][j][z][k] = max(f[i][j][z][k], f[i - 1][j][z][k] + so);
                    }
                    if (j >= 1)
                    {
                        f[i][j][z][k] = max(f[i][j][z][k], f[i][j - 1][z][k] + so);
                    }
                    if (z >= 1)
                    {
                        f[i][j][z][k] = max(f[i][j][z][k], f[i][j][z - 1][k] + so);
                    }
                    if (k >= 1)
                    {
                        f[i][j][z][k] = max(f[i][j][z][k], f[i][j][z][k - 1] + so);
                    }
                }
            }
        }
    }
    cout << f[num[1]][num[2]][num[3]][num[4]] + score[1] << endl;
    return 0;
}


活动打卡代码 AcWing 425. 明明的随机数

楚天
15天前
#include<bits/stdc++.h>
using namespace std;
int tong[20000000];
int n;
int big;
int num;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(tong[x]==0) num++;
        tong[x]++;
        big=max(big,x);

    }
    cout<<num<<endl;
    for(int i=1;i<=big;i++)
    {
        if(tong[i])
        {
            cout<<i<<' ';
        }
    }
}



活动打卡代码 AcWing 479. 加分二叉树

楚天
16天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e2;
int f[N][N], g[N][N];
int w[N];
int n;

void print(int l,int r)
{
    if(l>r) return;
    int k=g[l][r];
    cout<<k<<' ';
    print(l,k-1);
    print(k+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    for(int len=1;len<=n;len++)
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            for(int k=l;k<=r;k++)
            {

                int left=k==l?1:f[l][k-1];
                int right=k==r?1:f[k+1][r];
                int score=left*right+w[k];
                if(l==r)  score=w[k];
                if(f[l][r]<score) {f[l][r]=score;g[l][r]=k;}  
            }
        }
    cout<<f[1][n]<<endl;
    print(1,n);
}



活动打卡代码 AcWing 1402. 星空之夜

楚天
16天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
const double eps = 1e-6;
int n, m;
char g[N][N];
PII q[N * N];
int top;
double get_dist(PII a, PII b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double get_hash() {
    double sum = 0;
    for (int i = 0; i < top; i ++ )
        for (int j = i + 1; j < top; j ++ )
            sum += get_dist(q[i], q[j]);
    return sum;
}

char get_id(double key) {
    static double hash[30];
    static int id = 0;
    for (int i = 0; i < id; i ++ )
        if (fabs(hash[i] - key) < eps)
            return i + 'a';
    hash[id ++ ] = key;
    return id - 1 + 'a';
}

void dfs(int a, int b) {
    q[top ++ ] = {a, b};
    g[a][b] = '0';
    for (int x = a - 1; x <= a + 1; x ++ )
        for (int y = b - 1; y <= b + 1; y ++ ) {
            if (x == a && y == b) continue;
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '1')
                dfs(x, y);
        }
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == '1') {
                top = 0;
                dfs(i, j);
                char c = get_id(get_hash());
                for (int k = 0; k < top; k ++ )
                    g[q[k].x][q[k].y] = c;
            }
    for (int i = 0; i < n; i ++ ) cout << g[i] << endl;
    return 0;
}