【CF675C】Money Transfers（离散化，贪心）

http://www.cnblogs.com/chengsheng/p/5535316.html

题目大意：给你n个银行中的存款（负值表示借贷），是成环的，1跟n相接，这n个数的和为0。可以从i向i的相邻两侧转移存款，问你最少转移多少次，可以让所有银行的存款都为0。

解题思路：n个数的和为0，假设是由k个和为0的区间组成的。假设这些区间的长度为l_i，那么长度为l_i的区间需要l_i-1次转移。那么总共需要l₁-1+l₂-1+l₃-1...+l_k-1次转移，因为l₁+l₂+l₃...l_k=n，所以总共需要n-k次转移，这个k就是区间和为0的区间个数。我们通过求前缀和sum来统计区间和为0的个数。当sum[i] = sum[j]时，我们知道a[i+1]+...a[j]为0，这个区间和为0。所以我们记录sum=X出现的次数，n-time[X]来更新答案。

此题是均分纸牌(NOIP2002)强化（弱化？）版，此题1与n间可互换

C++自带离散化

排序里面MID没用INT64交了十多次终生遗憾

 var c,d:array[..]of longint;

     a,s:array[..]of  int64;

     n,i,ans:longint;

     t:int64;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 procedure qsort(l,r:longint);

 var i,j:longint;

     mid:int64;

 begin

  i:=l; j:=r; mid:=s[(l+r) div ];

  repeat

   while mid>s[i] do inc(i);

   while mid<s[j] do dec(j);

   if i<=j then

   begin

    t:=s[i]; s[i]:=s[j]; s[j]:=t;

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 begin

  read(n);

 // fillchar(s,sizeof(s),);

 // fillchar(c,sizeof(c),);

 // fillchar(d,sizeof(d),);

 //

  for i:= to n do read(a[i]);

  ans:=n-;

  for i:= to n do s[i]:=s[i-]+a[i];

  qsort(,n);

  for i:= to n do

   if (i=)or(s[i]>s[i-]) then c[i]:=c[i-]+

    else c[i]:=c[i-];

  for i:= to n do inc(d[c[i]]);

  for i:= to n do ans:=min(ans,n-d[i]);

  writeln(ans);

 end.

巴特西

【CF675C】Money Transfers（离散化，贪心）

最新文章

热门文章