频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
Hdu 2430 Beans (数据结构_单调队列)
2012-07-27 09:50:15           
收藏   我要投稿

题目大意:有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艹代码:
[cpp] 
#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); 
    } 

作者:woshi250hua
点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 队列
上一篇:UVa 10282 - Babelfish
下一篇:HDU-1258-Sum It Up
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站