Yali 2019-8-15 test solution

T1. 送货

Description

物流公司要用m辆车派送n件货物.货物都包装成长方体,第i件的高度为hi,重量为wi.因为车很小,一辆车上的货物必须垒成一摞.又因为一些不可告人的原因,一辆车上货物的重量在所有重量中大小排名要连续,但载重量却不限.每辆车的样子一模一样,车本身的最高点距地x,车的放货部位与地面平行,且上表面距地y.

一些快速通道有车辆高度限制,工作人员需要事先规划路线,他希望知道,当高度限制大于等于多少时,他有办法让所有货车都通过.

Input Format

第一行两个整数m,n.

第二行两个整数x,y.

第3~n+2行:第i+2行两个整数hi,wi.

Output Format

一个整数,表示答案.

Sample Input

3 5 3 2

1 5

5 4

4 3

2 2

4 1

Sample Output

Constraints

对于50%的数据:n,m<=20;

对于100%的数据:n,m<=1e5;0<hi,x,y<=1e5;0<wi<=1e9 且互不相同.

考场心路历程：

哇，　这道题一定是二分。

然后二分写炸。

看了std的标程，发现很妙，所以写一篇题解。

好了，solution开始。

这道题的思路:二分最小高度，判定是否可行，最后输出。

#include<bits/stdc++.h>

#define int long long //骚操作

using namespace std;

const int maxn = 100000 + 5;

int n, m, x, y, maxi;

struct node{

	int h, w;

}g[maxn];

// node 用来按重量排序

bool cmp(node x, node y){

	return x.w < y.w;

}

// 这里用了一点贪心思想， 矮一点的和一起也许可以凑一下尝试在一台货车内填的最多（~~ 玄学解释 ~~）

int sum; // 记录所有货物高度的和(因为你再怎么不好，把所有货物垒在一辆van上总是可以的)

bool pd(int top){

	int cnt = 0;//记录当前所用的van

    int NOW = 0;//记录当前货物的总高度

	for(int i = 1; i <= n; i ++){

		if(NOW + g[i].h > top){

		    //如果垒上这一个货物超过了桥洞

			cnt ++;

			//换车

			NOW = g[i].h;

		    //车上的高度

		} else {

			NOW += g[i].h;

		    //直接垒上

		}

	}

	return cnt < m;

	//介于NOW肯定不为零，所以还要加一辆货车。

	//可以写成 cnt + 1 <= m

}

signed main(){

//	freopen("send.in", "r", stdin);

//	freopen("send.out", "w", stdout);

	scanf("%lld%lld", &m, &n);

	scanf("%lld%lld", &x, &y);

	for(int i = 1; i <= n; i ++){

		scanf("%lld%lld", &g[i].h, &g[i].w);

	}

	sort(g + 1, g + 1 + n, cmp);

	//输入， 贪心地排序

	maxi = -1;

	//最高的一件货物为maxi

	for(int i = 1; i <= n; i ++){

		maxi = max(maxi, g[i].h);

		sum += g[i].h;

	    //更新maxi与sum

	}

	int l =	maxi, r = sum, ans;

    //二分下界至少为最大的货物， 上界为所有货物的和

//	cout << l << " " << r  << endl;

	while(l < r){

		int mid = l + r >> 1;

		if(pd(mid)){

			r = mid;

		} else {

			l = mid + 1;

		}

	}

	//二分过程

	printf("%lld", max(x, l + y));

	//l + y 加上van的载货平面高度，得和van的本身的高度比一比（加上货都不一定有车高）

	return 0;

}

[1]: file:///C:/Users/Administrator/AppData/Local/Microsoft/Windows/Temporary%20Internet%20Files/Content.IE5/6F8NP43S/solution%5B1%5D.pdf

T2 强迫症

Description

小X要给家里的走廊铺地毯.走廊的长度为m,小X买来了n条地毯,地毯的宽度都与走廊宽度相等,但长度不尽相同,第i条地毯长度为ai.小X对第i条地毯有ci的喜爱度.小X对地毯的喜爱度是一个关于地毯长度的固定高次函数.他希望铺上的地毯的喜爱度和最大,但小X有强迫症,他不能容忍地毯间或地毯与墙有任何重叠或缝隙.他需要你告诉他喜爱度和的最大可能值.若无法铺成,则输出-1.

Input Format

第一行两个整数,n和m.

以下有n行,每行两个正整数,表示一条地毯的长度和喜爱度.

Output Format

一行一个数,表示喜爱度和的最大可能值或-1.

Sample Input1

5 20

4 6

10 3

6 5

5 6

5 6

Sample Output1

Sample Input2

5 20

2 2

2 2

2 2

2 2

2 2

Sample Output2

-1

Explain for sample1

选出第1,3,4,5条地毯.

Constraints

对于30%的数据:m,n<=1000.

对于100%的数据:不同的长度个数<=2000;m<=10000;n<=2000000.ci<=1000000.ai<=1e9.

Hint

请使用较快的方式读入.

考场心路历程：数据表明肯定是单调队列优化dp（多重背包），30pts暴力做法水过

get30pts成功

solution开始

上面已经提到了，这道题只能单调队列优化

巴特西

Yali 2019-8-15 test solution

T1. 送货

Description

Input Format

Output Format

Sample Input

Sample Output

Constraints

T2 强迫症

Description

Input Format

Output Format

Sample Input1

Sample Output1

Sample Input2

Sample Output2

Explain for sample1

Constraints

Hint

最新文章

热门文章