暂无

专题

1. 树

还没有打比赛orz，稍微练了几道树的题

• 尺取法
• 前缀和

（由于我太菜了所以写一点基础的）

• 2020.05.05 Codeforces Educational Round #86
• 2020.05.08 Codeforces Round #639

(virtual participation)

给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小。数组中的数可正可负。

将前缀和排序，排序后每两个位置的前缀和之差代表一个原来的区间的和的绝对值(妙啊），同时在这个排序后的前缀和序列中随区间增缩所取的区间和的绝对值也增缩。这样运用尺取法是一个好的选择。

  #include<cstdio>
  #include<algorithm>
  #define INF 0x3f3f3f3f
  using namespace std;
  int n,k,a;
  typedef pair<int,int> unit;
  unit sum[100005];
  int main()
  {
      while(scanf("%d%d",&n,&k)&&n)
      {
          for(int i=1;i<=n;i++)
          {
              scanf("%d",&a);
              sum[i]=unit(sum[i-1].first+a,i);
          }
          sort(sum+1,sum+1+n);
          for(int i=1;i<=k;i++)
          {
              scanf("%d",&a); 
              int t=INF,l,r;
              for(int left=1,right=1;right<=n;right++)
              {
                  while(sum[right].first-sum[left].first>a)
                  {
                      if(sum[right].first-sum[left].first-a<t)
                      {
                          t=sum[right].first-sum[left].first-a;
                          l=sum[left].second;
                          r=sum[right].second;
                      }
                      left++;
                  }
                  if(a-sum[right].first+sum[left].first<t)
                  {
                      t=a-sum[right].first+sum[left].first;
                      l=sum[left].second;
                      r=sum[right].second;
                  }
              }
              printf("%d %d %d\n",sum[r].first-sum[l].first,l,r);
          }
      }
      return 0;
  }