二号阵容到二号窗口去排队打饭,以后给定N个人

作者:澳门娱乐

Description

中午的磨练停止了,THU ACM小组集体去吃午饭,他们一行N人来到了盛名的十酒楼。这里有五个打饭的窗口,每种窗口同样时刻只可以给一人打饭。由于各样人的意气(以及食欲)不相同,所以她们要吃的菜各有差别,打饭所要开支的小时是因人而异的。别的每一种人用餐的进度也不尽同样,所以吃饭费用的时刻也是唯恐天冠地屦的。 THU ACM小组的用餐安排是那样的:先把持有的人分为两队,并计划好每队中每人的排列顺序,然后一号阵容到一号窗口去排队打饭,二号队容到二号窗口去排队打饭。每种人打完就餐之后及时初始吃,全数人都吃完用完餐之后及时集结去六教地下室实行午夜的磨练。 现在给定了每一个人的打饭时间和吃饭时间,须求配置一种超级的分队和排队方案使得全体人都吃完饭的时间尽恐怕早。 若是THU ACM小组在时刻0到达十饭馆,何况客栈里面未有其他吃饭的同窗(独有打饭的师父)。每种人无法不一致一时候只好被分在一个部队里。五个窗口是并行操作互不影响的,而且每一种人打饭的光阴是和窗口非亲非故的,打完饭之后马上就开头进食,中间未有延迟。 未来给定N个人分其他打饭时间和吃饭时间,须求输出最棒方案下全数人吃完饭的时刻。

Description

中午的教练甘休了,THU ACM小组集体去吃中饭,他们一行N人来到了盛名的十饭铺。这里有多个打饭的窗口,每种窗口相同时刻只可以给壹位打饭。由于种种人的气味(以及食欲)分歧,所以她们要吃的菜各有差别,打饭所要开支的时间是一碗水端平的。别的各类人吃饭的进程也不尽一样,所以吃饭费用的时日也是大概天地之别的。 THU ACM小组的用餐安插是这么的:先把全数的人分成两队,并布置好每队中每人的排列顺序,然后一号阵容到一号窗口去排队打饭,二号阵容到二号窗口去排队打饭。每一种人打完用完餐之后随即起先吃,全体人都吃完就餐之后当即集结去六教地下室举办中午的教练。 以后给定了各样人的打饭时间和吃饭时间,供给配置一种一级的分队和排队方案使得全体人都吃完饭的时刻尽量早。 假使THU ACM小组在时刻0达到十茶楼,何况饭店里面未有别的吃饭的校友(唯有打饭的师傅)。各类人必需同一时候不得不被分在三个兵马里。七个窗口是并行操作互不影响的,何况各样人打饭的时光是和窗口非亲非故的,打完饭之后随即就初叶吃饭,中间未有延迟。 今后给定N个人分其余打饭时间和吃饭时间,须要输出最棒方案下全部人吃完饭的时刻。

Input

先是行八个卡尺头N,代表共计有N个人。 以下N行,每行五个整数 Ai,Bi。依次代表第i民用的打饭时间和吃饭时间。

Input

率先行一个整数N,代表共计有N个人。 以下N行,每行多个整数 Ai,Bi。依次代表第i私人商品房的打饭时间和吃饭时间。

Output

一个板寸T,代表全体人吃完饭的最先时刻。

Output

八个莫西干发型T,代表全数人吃完饭的最先时刻。

Sample Input

5
2 2
7 7
1 3
6 4
8 5

Sample Input

5
2 2
7 7
1 3
6 4
8 5

Sample Output

17

Sample Output

17

HINT

方案如下:

窗口1: 窗口2:
7 7 1 3
6 4 8 5
澳门娱乐6165,2 2

【限制】
富有输入数据均为不超过200的正整数。

HINT

方案如下:

窗口1: 窗口2:
7 7 1 3
6 4 8 5
2 2

【限制】
怀有输入数据均为不超越200的正整数。

 

题解:

那题未有和谐想出去啊.....依然太渣

首先那题状态里应该要一时光,轻松想到f[i][j][k] 表示前i人第一窗口甘休时间为j,第二窗口甘休时间为k的蝇头甘休时刻

开不下呀 咋办? 偷瞄一眼题解....恩两维

下一场继续想,分明j+k正是i的前缀和sum[i]呀....那么消掉一维,开得下了,並且首先位可以滚掉可能差相当少不要,但没须求

码完开掘那题就疑似还应该有一个吃饭时间,好像不可能差不离枚举i啊.....又去瞄眼题解

见状排序两字,又想,好像挺有道理,果决按吃饭时间长短排序,因为排队总时间是早晚的,那么最后竣事作时间间只跟吃饭时间有关,那么就想开吃饭时间长的先吃....

然后sort之后就1A了

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=305,M=40015;
 9 int f[N][M];
10 struct node{
11     int w,val;
12 }a[N];
13 bool comp(const node &pp,const node &qq){
14     return pp.val>qq.val;
15 }
16 int sum[N];
17 void work()
18 {
19     int n;
20     scanf("%d",&n);
21     for(int i=1;i<=n;i++)scanf("%d%d",&a[i].w,&a[i].val);
22     sort(a+1,a+n+1,comp);
23     for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].w;
24     memset(f,127/3,sizeof(f));
25     int inf=f[0][0];
26     f[0][0]=0;
27     for(int i=0;i<n;i++){
28         for(int j=0;j<=sum[i];j++){
29             if(f[i][j]==inf)continue;
30             f[i+1][j+a[i+1].w]=min(f[i+1][j+a[i+1].w],max(j+a[i+1].w+a[i+1].val,f[i][j]));
31             f[i+1][j]=min(f[i+1][j],max(f[i][j],a[i+1].val+sum[i]-j+a[i+1].w));
32         }
33     }
34     int ans=2e8;
35     for(int i=0;i<=sum[n];i++){
36         if(f[n][i]<ans)ans=f[n][i];
37     }
38     printf("%dn",ans);
39 }
40 int main()
41 {
42     work();
43     return 0;
44 }

 

Source

题解

那题未有和谐想出去QAQ

其实如若唯有三个窗口这正是精粹贪心题,对吃饭时间举办排序,吃饭时间长的先打饭(因为总的打饭时间是早晚的)

先保留上边的主张,想想别的做法

咱俩得以设$f[i][j][k]$表示前i个人在1窗口打饭时间为j,在2窗口打饭为k的最优解

不过j和k这两维都得开到陆仟0(200*200)

设想优化空间。开掘只要对打饭时间保卫安全贰个前缀和,那么就可以只保留三个光阴了,其他一个时光则是$sum[i]-j$

思索更改(方程里面包车型客车c[i]是前缀和)

对此在1窗口打饭的意况:$f[i][j]=min(f[i][j],max(f[i-1][j-a[i].x],j+a[i].y))$ 

对此在2窗口打饭的动静:$f[i][j]=min(f[i][j],max(f[i-1][j],c[i]-j+a[i].y))$

那正是说最优解便是在$f[n][1...c[n]]$里面找了

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

struct node {
    int x,y;
}a[300];

int h1,h2,n;
int c[300],f[300][40000];
//f[i][j]表示前i个人时其中一个队伍打饭时间为j的最优解 
//c数组维护前缀和 

bool cmp(node a,node b){
    return a.y>b.y;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }

    memset(f,0x3f,sizeof(f));
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)c[i]=c[i-1]+a[i].x;

    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=c[i];j++){
            f[i][j]=min(f[i][j],max(f[i-1][j],c[i]-j+a[i].y));
            //在另外一个窗口吃 
            if(j-a[i].x>=0)f[i][j]=min(f[i][j],max(f[i-1][j-a[i].x],j+a[i].y));
            //在当前窗口吃 
        }
    }

    int ans=0x3f3f3f3f;
    for(int i=0;i<=c[n];i++){
        ans=min(ans,f[n][i]);
    }
    printf("%dn",ans);

    return 0;
}

 

本文由澳门娱乐6165发布,转载请注明来源

关键词: