第一篇做题记录：cf872div2

• 意思是固定最左上角的一个数，然后移动右下角，框出的矩形里面找最大最小值，相减，然后累加。

• 输入是输入这么多个数字，是可以自己排列在表里的。

• 思路：输入长宽的时候长在前宽在后，就是如果m<n要互换一下保证m>n.然后将填入的数组排一下序，一种做法是最左上角填入最大的数，然后这个位置的右方填入最小的数，下方填入第二小的数，可以证明这样相减得到的较大的值占的位置比较多。另一种做法是最左上角填入一个最小的数，这个位置的右方填入最大的数，下方填入第二大的数，两种做法分别求sum，最后比较这两个sum，求最大值就是ans。

• 

• 代码：

  #include "bits/stdc++.h"
  using namespace std;
  /**/
  int a[105][105],b[100005];
  int main()
  {
      int n;
      cin>>n;
      while(n--){
          long long sum1=0,sum2=0;
          int p,q;
          cin>>p>>q;
          int tmp;
          if(p<q){
              tmp=p;
              p=q;
              q=tmp;
              
          }
          int x=p*q;
          for(int i=1;i<=x;i++) cin>>b[i];
          sort(b+1,b+1+x);
          sum1=(p-1)*q*(b[x]-b[1])+(q-1)*(b[x]-b[2]);
          sum2=(p-1)*q*(b[x]-b[1])+(q-1)*(b[x-1]-b[1]);
          long long ans=max(sum1,sum2);
          
          cout<<ans<<endl;
      }
      
      return 0;
  }

  

• 题目大致意思就是有一排空的座位，现在有m个人，每个人对作座位的选择不同，-1代表坐在最左边的人的左边，如果现在没有人，那久坐在座位的最右边，-2和-1相反，代表坐在最右边的人的右边，如果现在没有一个人，那就坐在座位的最左边，其他>0的选择就坐在对应选择的位置上，以上如果位置有人坐 了那他就离开，求一个方案能让尽量多的人坐上座位，实际上就是给一个入座的顺序使得他们能根据不同的需求坐上座位，使这个人数尽量多。

• 想法：
  首先，如果有两个人都想坐Xi，那他们只能有一个人坐在那里。

  然后，直接坐Xi位置的人不会影响前两种情况，例如：

  >>>4>>7<<10<<13

  你可以通过先放置一个情况三，在他两侧放置前两种情况的人，放置过程中如果当前位置有第三种人指定要坐，就i让他坐，然后继续排前两种情况。

  所以Xi的人坐进去一定不会使答案变差。

  然后以所有Xi作为中间点，进行上述排布求得1和2情况的最大排布数量，取个max，再加上Xi的数量，就是一般的情况。

  ans = max( ans , min( i - v[i] , lf ) + min( m - ( v[m] - v[i] ) - i , ri ) );

  v数组是Xi分布的前缀和，lf和ri是左右两种坐法的数量。

  特殊的，我们可以或者只能从一侧开始排布，（即没有1或者2的情况），只需要对0和m+1作上述操作。

  然后使用前缀和使得算法变成o（n）的时间复杂度。

• 代码：

  #include "bits/stdc++.h"
  using namespace std;
  int a[100005];
  int b[100005];
  int main()
  {
      int n;
      cin>>n;
      while(n--){
          int k,m;
          cin>>k>>m;
          int ans=0;
          int cnt1=0,cnt2=0;
          int idx=0;
          
          for(int i=1;i<=k;i++){
             int x;
              cin>>x;
              if(x==-1){cnt1++;continue;}
              if(x==-2){cnt2++;continue;}
            
              if(b[x]!=0) continue;
              b[x]=1;
              a[++idx]=x;//去重
          }
          
          
         for(int i=1;i<=m+1;i++) b[i]+=b[i-1];
          
          for(int i=1;i<=m;i++){
              if(b[i]-b[i-1]){
                  ans=max(ans,min(i-b[i],cnt1)+min(m-(b[m]-b[i])-i,cnt2));
              }
          }
          ans=max(ans,min(m-(b[m]-b[0]),cnt2));
          ans=max(ans,min(m-b[m],cnt1));
          cout<<ans+idx<<endl;
          memset(b,0,sizeof(b));
      }
      
      return 0;
  }

Donate