头像

明天会更好_7




离线:2天前


最近来访(0)

活动打卡代码 AcWing 790. 数的三次方根

#include<iostream>
using namespace std;

int main(){
    double n;
    double l=-10000,r=10000,mid;

    scanf("%lf",&n);

    while(r-l > 1e-8){
        mid=(l+r)/2;
        if(mid*mid*mid >= n) r=mid;
        else l=mid;
    }

    printf("%.6lf",l);
}



活动打卡代码 AcWing 789. 数的范围

#include<iostream>
using namespace std;

int const N=1000010;
int p[N];

int main(){
    int n,q,k;

    scanf("%d%d",&n,&q);

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

    while(q--){
        int l=0,r=n-1;

        scanf("%d",&k);

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

            if(p[mid]>=k) r=mid;

            else l=mid+1;
        }
        if(p[l]!=k){
            cout<<"-1 -1"<<endl;
        }
        else{
            cout<<l<<' ';

            int l=0,r=n-1;

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

                if(p[mid]<=k) l=mid;

                else r=mid-1;
            }
            cout<<l<<endl;
        }

    }
}


活动打卡代码 AcWing 787. 归并排序

#include<iostream>
using namespace std;

int const N=1e6 + 10;
int q[N],p[N];

void merge_sort(int q[],int l,int r){
    if(l >= r) return;

    int mid=(l+r)>>1;

    merge_sort(q,l,mid),merge_sort(q,mid+1,r);

    int k=0,i=l,j=mid+1;

    while(i<=mid&j<=r){
        if(q[i]<=q[j]) p[k++]=q[i++];
        else p[k++]=q[j++];
    }
    while(i<=mid) p[k++]=q[i++];
    while(j<=r) p[k++]=q[j++];

    for(k=0,i=l;i<=r;k++,i++) q[i]=p[k];
}

int main(){
    int n;

    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    merge_sort(q,0,n-1);

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


活动打卡代码 AcWing 786. 第k个数

#include<iostream>
using namespace std;

const int N=1e6 + 10;

int q[N];

void quick_sort(int q[],int l,int r){
    if(l >= r) return;

    int i = l-1,j = r+1,x=q[(l + r) >> 1];

    while(i < j){
        do i++;while(q[i] < x);
        do j--;while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }

    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int main(){
    int n,k;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    quick_sort(q,0,n-1);

    printf("%d",q[k-1]);
}


活动打卡代码 AcWing 785. 快速排序

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;

const int N=1e6 + 10;

int n;
int q[N]; //注意要设为全局变量

void quick_sort(int q[],int l,int r){

    if(l >= r) return;

    int i = l - 1,j = r + 1,x = q[l + r >> 1];

    while(i < j){

        do i++;while(q[i] < x);

        do j--;while(q[j] > x);

        if(i < j) swap(q[i] , q[j]); 
    }

    quick_sort(q,l,j);

    quick_sort(q,j + 1,r);
}

int main(){

    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    quick_sort(q,0,n-1);

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

    return 0;
}



AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/81679/




AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/81679/



新鲜事 原文

AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/


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

明天会更好_7
2021-02-03 22:18
#include<stdio.h>
#define N 110
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
int n;
int h[N];
int f[N], g[N];
int i,j;
int main()
{
    scanf("%d", &n);
    for ( i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    for (i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (j = 1; j < i; j ++ )
            if (h[j] < h[i])
                f[i] = max(f[i], f[j] + 1);
    }

    for (i = n; i; i -- )
    {
        g[i] = 1;
        for (j = n; j > i; j -- )
            if (h[j] < h[i])
                g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    for (i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);

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

    return 0;
}



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

明天会更好_7
2021-02-03 17:01
#include<stdio.h>
void sort(int *a, int left, int right)
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];

    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升
        序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }

        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是
        a[left],那么就是给key)*/

        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,
        因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }

        a[j] = a[i];
    }

    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/
}
int main()
{
    int n,i;
    scanf("%d",&n);
    int a[100010],s=0;
    for(i=0;i<n;++i) {
        scanf("%d",&a[i]);
        s+=a[i];
    }
    sort(a,0,n-1);
    int s1=0;
    for(i=0;i<n/2;++i)
    {
        s1+=a[i];
    }
    printf("%d %d",n%2,s-2*s1);
}