首页 > ACM题库 > HDU-杭电 > hdu 2430 Beans-Google-[解题报告]C++
2014
01-26

hdu 2430 Beans-Google-[解题报告]C++

Beans

问题描述 :

      Mr. Pote’s shop sells beans now. He has N bags of beans in his warehouse, and he has numbered them with 1, 2, …, N according to their expired dates. The i-th bag contains Wi units of beans. For selling at retail makes only a little profit, Mr. Pote want to pack beans in small packets with certain size and sell them in packets. Here comes his packing way:
      Suppose the size of the packet is P units. Firstly, Mr. Pote selects some bags (at least one) of beans with consecutive number in his warehouse. Then he takes out the beans from all selected bags, and puts them together on the desktop. To pack the beans, he take P units of beans from desktop and fill in a new packet each time, until the beans left are less than P units. Finally the beans left on the desktop are eaten by a lucky dog.
      Mr. Pote doesn’t want the dog eat too many beans, so he prefers to solutions that resulting no more than K units of beans eaten by the dog. Moreover, he also wants to pack as many packets as possible. Could you tell him how many packets he can pack at most without breaking his preference?

输入:

      On the first line of input, there is a single positive integer T <= 20 specifying the number of test cases to follow.
      Each test case contains two lines.
      There are three integers in the first line, N, P, K as described above. (0 < N, P < 1000001, 0 <= K < P)
      Next follow a line with N integers W1, W2, …, WN. The i-th integers describes the amount of beans in the bags numbered i. (0 <= Wi < 32768)
      Numbers are separated by spaces.

输出:

      On the first line of input, there is a single positive integer T <= 20 specifying the number of test cases to follow.
      Each test case contains two lines.
      There are three integers in the first line, N, P, K as described above. (0 < N, P < 1000001, 0 <= K < P)
      Next follow a line with N integers W1, W2, …, WN. The i-th integers describes the amount of beans in the bags numbered i. (0 <= Wi < 32768)
      Numbers are separated by spaces.

样例输入:

3
10 20 10
0 3 1 8 19 39 2 9 1 8
3 100 10
32 34 23
1 5 3
1

样例输出:

Case 1: 4
Case 2: -1
Case 3: 0

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2430

题目大意:有n坨豌豆,每坨都有w[i]个,现在要从中选择连续的若干坨,然后用一个能装p个豌豆的背包装豆子,直到剩下的豌豆数量<=p为止,还要求剩下的豌豆数量少于k,问最多能装多少包。

解题思路:题意很明了,模型也很好抽象。本题就是要选择连续的一段和为sum,使得max(sum/p) 且sum%p<=k。那么要怎么算这个sum呢?这里就大有文章可做了。

    其实这类求区间和的问题很经常是用sum[i]- sum[j-1]这种方式来表达的,我们设sum[i]表示0到i坨豌豆的总数量,那么上面的sum就是sum[i]-sum[j-1]。从而得到一个式子,max(sum[i]-sum[j]) (j < i && (sum[i]-sum[j])%p<=k),表示以i为区间尾,因为豌豆数量非负数,那我们向前找个最小的下标使得差最小且符合条件即可。

    我们设sum[i]为x,sum[j]为y,那么上式变成0<=(x-y)%p<=k且x-y最大,约束条件是x大等于y,我们要利用这些条件快速地找到x对应的那个最小的y。

    0<=(x-y)%p<=k  –>  0<=(x%p – y%p + p) % p<=k

    如果x%p >= y%p,那么x%p-k<=y%p<=x%p,我们就可以根据x%p来定位y%p.

    如果x%p < y%p,那么我们可以换个角度想,在以y结尾的时候就会有上面的情况。

    那问题就剩下一个了,如果根据x%p来快速定位y%p。写法有多种,用线段树和树状数组都可以写,但我用线性的单调队列来写,时间78ms,是提交记录的第二名。

    我先将每个和对p取余得到一个余数r数组,然后按余数大小优先位置其次的顺序排序。排完序之后就可以根据ri – k <= rj <= ri来往前找那个最小的j。遍历数组r,因为r是有序的,我用单调队列储存r小于当前的最小下标。关于单调队列,我就不多说了,百度google去。最后更新答案即可。

    总复杂度还是(nlogn),主要用于排序。

测试数据:

20
2 19 3
17 3
Out:Case 1: 1


2 19 1

17 3
Out:Case 2: 1


2 19 3

17 6
Out:Case 3: -1


10 20 10

0 3 1 8 19 39 2 9 1 8

Out:Case 4: 4


3 100 10

32 34 23
Out:Case 5: -1


1 5 3

5
Out:Case 6: 1


5 15 4

7 8 3 10 10
Out:Case 7: 2


C艹代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 1000010
#define max(a,b) (a)>(b)?(a):(b)


struct node {
    
    int x,in;
}r[MAX],qu[MAX];
__int64 sum[MAX],ans;
int head,tail;
int n,p,k,mmin[MAX];


int cmp(node a,node b) {
    
    if (a.x == b.x) return a.in < b.in;
    else return a.x < b.x;
}
void Solve_AC() {
	
	int i,j;
	head = 0,tail = 1;


	for (i = 1; i <= n; ++i) {
		
		if (tail > head) mmin[r[i].in] = -1;
		else mmin[r[i].in] = qu[tail].in;


		while (tail <= head 
			&& r[i].in < qu[head].in)  head--;


		qu[++head] = r[i];
		while (tail <= head && r[i + 1].x - qu[tail].x > k)
			tail++;
	}
	
	
	for (i = 1; i <= n; ++i) {
		
		if (sum[i] % p <= k) ans = max(ans,sum[i] / p);
		if (mmin[i] == -1 || mmin[i] >= i) continue;
		ans = max(ans,(sum[i] - sum[mmin[i]]) / p);
	}
}


int main()
{
    int i,j,t,cas = 0;
    
    
    scanf("%d",&t);
    while (t--) {
        
        scanf("%d%d%d",&n,&p,&k);
        for (i = 1; i <= n; ++i) {
            
            scanf("%d",&sum[i]);
            r[i].in = i;
            sum[i] +=  sum[i-1];
            r[i].x = sum[i] % p;
        }
        
        
        sort(r+1,r+1+n,cmp);
		ans = -1,Solve_AC();
        printf("Case %d: %I64d\n",++cas,ans);
    }
}

本文ZeroClock原创,但可以转载,因为我们是兄弟。

解题转自:http://blog.csdn.net/woshi250hua/article/details/7791656


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge