网易笔试题-双核处理

101 阅读 0 评论 67 点赞

我是靠谱客的博主繁荣柜子，最近开发中收集的这篇文章主要介绍网易笔试题-双核处理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)
第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。

输出描述:
输出一个整数，表示最少需要处理的时间

输入例子:
5
3072 3072 7168 3072 1024

输出例子:
9216

#include"stdio.h"
#include"algorithm"
#include"iostream"
#include"math.h"
#include"string.h"
using namespace std;
int f[51][40000];
int main()
{
    memset(f, 0, sizeof(f));
    int N;
    int ai[51],bi[51];
    bool sign[51];

    scanf("%d",&N);
    int he=0;

    for(int i = 0; i < N; i++)
    {
        scanf("%d", &bi[i]);
        ai[i] = bi[i]/1024;
        he += ai[i];
    }
    for(int j=1; j<=he/2; j++)
        f[0][j]=0;
    for(int i=0; i<=N; i++)
        f[i][0]=0;
    for(int i=1;i<=N;i++)
    {

        for(int j=1;j<=he/2;j++)
        {
            f[i][j]=f[i-1][j];
            if(ai[i]<=j && f[i-1][j-ai[i]]+ai[i]>f[i][j]){
                f[i][j]=f[i-1][j-ai[i]]+ai[i];
            }
        }

    }
    printf("%dn", (he-f[N][he/2])*1024);
    return 0;
}

动态规划，其实就是简单的背包问题

代码还未提交2017/3/25

下面贴出ac代码 2017/4/6

#include"stdio.h"
#include"algorithm"
#include"iostream"
#include"math.h"
#include"string.h"
using namespace std;
int f[52][110000];
int main()
{
    memset(f, 0, sizeof(f));
    int N;
    int ai[51],bi[51];
    bool sign[51];

    scanf("%d",&N);
    int he=0;

    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &bi[i]);
        ai[i] = bi[i]/1024;
        he += ai[i];
    }
    //cout<<he<<endl;
    memset(f,0,sizeof(f));
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=he/2;j++)
        {
            f[i][j]=f[i-1][j];
            if( j>=ai[i]&&f[i-1][j-ai[i]]+ai[i]>f[i][j]){
                f[i][j]=f[i-1][j-ai[i]]+ai[i];
            }
        }

    }

    printf("%dn", (he-f[N][he/2])*1024);
   // printf("%dn", f[N][he/2]*1024);
    return 0;
}