bzoj 2802: [Poi2012]Warehouse Store 題解

【原題】

Description

有一家專賣一種商品的店，考慮連續的n天。
第i天上午會進貨Ai件商品，中午的時候會有顧客需要購買Bi件商品，可以選擇滿足顧客的要求，或是無視掉他。
如果要滿足顧客的需求，就必須要有足夠的庫存。問最多能夠滿足多少個顧客的需求。

Input

第一行一個正整數n (n<=250,000)。
第二行n個整數A1,A2,...An (0<=Ai<=10^9)。
第三行n個整數B1,B2,...Bn (0<=Bi<=10^9)。

Output

第一行一個正整數k，表示最多能滿足k個顧客的需求。
第二行k個依次遞增的正整數X1,X2,...,Xk，表示在第X1,X2,...,Xk天分別滿足顧客的需求。

Sample Input

Sample Output

【分析】這道題我被坑的好久。

首先這肯定是貪心。我開始是這樣想的：我們把顧客要求的多少排序，然後每次看看第I個顧客是否能給他，如果能的話就賣給他並更新我目前的錢。如果用f[i]表示到第i天剩余的錢的話，如果第K天的東西我賣了，我會把K+1~N的所有f元素都減去第K天顧客的要求數量。HHD表示應該減去1--K-1的f值。我們馬上碼好發現WA了。

【初始代碼（開始用樹狀數組，後來怕寫萎了，改成線段樹了）】

#include
#include
#define L(x) (x&-x)
#define N 250005
using namespace std;
typedef long long ll;
ll f[N],data[N],write[N],temp,x,y,jia,n,i,ans,sum;
struct arr{ll x,id;}b[N];
struct arr2{ll l,r,sum,add;}a[N*4];
char opt[5];
inline void build(ll k,ll l,ll r)
{
  a[k].add=0ll;a[k].l=l;a[k].r=r;
  if (l==r) {a[k].sum=data[l];return;}
  ll mid=(l+r)>>1;
  build(k<<1,l,mid);build((k<<1)+1,mid+1,r);
  a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum;
}
inline void down(ll k)
{
  if (a[k].add==0) return;
  a[k<<1].sum+=a[k].add*(a[k<<1].r-a[k<<1].l+1ll);
  a[(k<<1)+1].sum+=a[k].add*(a[(k<<1)+1].r-a[(k<<1)+1].l+1ll);
  a[k<<1].add+=a[k].add;a[(k<<1)+1].add+=a[k].add;
  a[k].add=0;
}
void update(ll k)
{
  if (a[k].l>=x&&a[k].r<=y) 
  {
    a[k].sum+=jia*1ll*(a[k].r-a[k].l+1ll);
    a[k].add+=jia;return;
  }
  down(k);
  ll mid=(a[k].l+a[k].r)>>1;
  if (x<=mid) update(k<<1);
  if (y>mid) update((k<<1)+1);
  a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum;
}
ll ask(ll k)
{
  if (a[k].l>=x&&a[k].r<=y) return a[k].sum;
  down(k);
  ll mid=(a[k].l+a[k].r)>>1;ll o=0;
  if (x<=mid) o+=ask(k<<1);
  if (y>mid) o+=ask((k<<1)+1);
  a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum;
  return o;
}
inline ll Read()
{
  char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar());
  ll x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10ll+ch-'0';
  return x;
}
//inline void add(ll x,ll v){if (!x) return;for (;x<=n;x+=L(x)) f[x]+=v;}
//inline ll ask(ll x){ll s=0;for (;x;x-=L(x)) s+=f[x];return s;}
inline bool cmp(arr a,arr b){return a.x=b[i].x) x=i,y=n,jia=-b[i].x,update(1),write[++ans]=b[i].id;
  }
  sort(write+1,write+ans+1);
  printf("%lld\n",ans);
  for (i=1;i<=ans;i++) printf("%lld ",write[i]);
  return 0;
}

原來這樣的更新是有問題的，無論是前面還是後面減，都有嚴重的類似後效性的東西。

經過SYC大神的指導，有一種完美的解決方案：從第一天開始每次判斷當前的東西可不可以賣。如果可賣就賣掉並壓入堆。如果賣不掉（缺貨），去之前的堆中找最大值比較一下並決定是否賣。

【AC代碼】

#include
#include
#include
#define N 250005
using namespace std;
typedef long long ll;
typedef pairPair;
Pair temp;
priority_queueq;
inline ll Read()
{
  char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar());
  ll x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
  return x;
}
ll a[N],b[N],ans[N],now,n,i,big,id,cnt;
int main()
{
  n=Read();
  for (i=1;i<=n;i++) a[i]=Read();
  for (i=1;i<=n;i++) b[i]=Read();
  for (i=1;i<=n;i++)
  {
    now+=a[i];
    if (now>=b[i]) now-=b[i],q.push(make_pair(b[i],i)),ans[i]=1;
    else if (!q.empty())
    {
      temp=q.top();big=temp.first;id=temp.second;
      if (big>b[i]) q.pop(),ans[id]=0,now+=(big-b[i]),q.push(make_pair(b[i],i)),ans[i]=1;
    }
  }
  for (i=1;i<=n;i++) if (ans[i]) cnt++;
  printf("%lld\n",cnt);
  for (i=1;i<=n;i++) if (ans[i]) printf("%d ",i);
  return 0;
}