zoj 3606 Lazy Salesgirl (线段树，单点更新，区间合并)

2017-09-26 · 3 min read · 线段树

zoj3606题目链接

题意：有个小女孩卖火柴,有n个人会来买，分别在时间t[i]，以价格p[i]，买的火柴个数为1+(k-1)%3,其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴，小女孩就会睡着。小女孩睡着后如果有人来买火柴，那小女孩就会醒过来，但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。

思路： 显然，w应该是某2个顾客的来访时间只差（而不是什么任意值）.

因此我们可以通过枚举相邻访问时间的顾客的访问之间之差。

我们可以从小到大枚举w，这样就可以保证得到的最大营业额的对应w最小。

构造一颗线段树，维护4个域，cnt表示区间中，确实购买了火柴的顾客的人数，sum[i] (i属于0..2) 表示一个区间中最左边的顾客购买了i+1根火柴后，该区间的最大利润。

所以其实这道题类似hdu4288解题报告           

维护sum[i]的时候，右一点绕，需要注意对于tree[rt].sum[i]，我们只是说该区间的最左边的人买了(i+1)根火柴，该区间的其他人买了几根火柴无所谓，我们只想知道该区间的利润。

wa了一次。。因为虽然我们分析出w一定是某2个连续的时间的差值，一定是整数值，但是为了迷惑人。。题目还是要以6位小数输出。

/* ***********************************************
Author :111qqz
Created Time :2017年09月26日 星期二 18时32分43秒
File Name :3606.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7int n;
 8int total;
 9struct node
10{
11    int p,t;
12    int id;
13    bool operator < (const node &b) const
14    {
15    return t<b.t;
16    }
17}a[N],b[N];

1struct Tree
2{
3    LL sum[3];//sum[i]表示当区间最左边的人买了i+1个面包时，该段区间的总销售额
4    int cnt;
5}tree[N<<2];

 1void PushUp(int rt)
 2{
 3    tree[rt].cnt = tree[rt<<1].cnt + tree[rt<<1|1].cnt;
 4    int len = tree[rt<<1].cnt;
 5    for ( int i = 0 ; i < 3 ; i++)
 6    {
 7    tree[rt].sum[i] = tree[rt<<1].sum[i] + tree[rt<<1|1].sum[(i+len)%3];
 8    //区间合并有点绕
 9    //将区间rt<<1和rt<<1|1合并到rt的时候，需要注意，我们只规定了区间rt的最左端的人是买了i+1个面包。
10    //rt<<1|1区间的人买了几个面包无所谓，我们只要求这个销售额。
11    }

 1}
 2void update( int x,int l,int r,int rt)
 3{
 4    if (l==r)
 5    {
 6    for ( int i = 0 ; i < 3 ; i++) tree[rt].sum[i] = 1LL*(i+1)*a[x].p;//printf("i:%d x:%d a[x]:%d sum[i]:%lld \n",i,x,a[x].p,tree[rt].sum[i]);
 7    tree[rt].cnt=1;
 8    return;
 9    }
10    int m = (l+r)>>1;
11    if (x<=m) update(x,lson);
12    else update(x,rson);
13    PushUp(rt);
14}
15int main()
16{
17    #ifndef  ONLINE_JUDGE 
18    freopen("./in.txt","r",stdin);
19  #endif
20    int T;
21    cin>>T;
22    while (T--)
23    {
24        total = 0 ;
25        ms(tree,0);
26        scanf("%d",&n);
27        for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i].p);
28        for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i].t);
29        sort(a+1,a+n+1);

 1        a[0].t=0;
 2        for ( int i = 1 ; i <= n ; i++)
 3        {
 4        b[i].t = a[i].t-a[i-1].t;
 5        b[i].p = a[i].p;
 6        b[i].id = i ;
 7        }
 8        sort(b+1,b+n+1);
 9       /* 
10        for ( int i = 1 ; i <= n ; i++)
11        {
12        printf("id:%d w:%d p:%d\n",b[i].id,b[i].t,b[i].p);
13        }
14        */

 1        double mx =  0.0;
 2        double  ans_w;
 3        for ( int i=1,j=1; i <= n ; i=j) 
 4        {
 5        while (b[i].t==b[j].t&&j<=n)  //一样的要一起处理，否则可能得到不合理的平均值。
 6        {
 7            total++;
 8            update(b[j].id,1,n,1);
 9    //      cout<<tree[1].sum[0]<<endl;
10            j++;
11        }
12        double ave = tree[1].sum[0]*1.0/total;
13        //cout<<"total:"<<total<<endl;
14        if (ave>mx)
15        {
16            mx = ave;
17            ans_w = b[j-1].t;
18        }
19        }
20        printf("%.6f %.6f\n",ans_w,mx);
21    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}