参考视频

J

题意:在十字路口中，给定四个方向上所有车以及转向情况，每辆车完成转弯需要一秒，求在不违反交通规则的情况下最少需要多少秒使得所有车都完成转向。
思路:
1，车辆右转是不受限制的，使得每个方向上至多只有左转和直行两种情况。
2，在一的基础上，可以知道整个十字路口不能有三盏以上的绿灯(不考虑右转的灯)。
我们就可以生成一个2X4的矩阵，表示每个方向上直行和左转的车数。

对于一个方向两盏绿灯只有四种情况

这四种方向表示对应着

易知，不考虑情况三，我们发现这是在一个2X2的矩阵里面，每次使一行或一列的两个数减一。要使所有的数都小于等于0，需要操作的最小次数是 ，现在我们考虑情况三，它无非就是对角线上减一，一共有四条对角线，我们枚举其中三条（少枚举一条是因为四条中总有一条是最小的，我们可以不考虑这条最小的，对它直接进行操作）（不能理解看一下参考视频）。最后再将得到的答案与右转相比较得到最终答案。

#include<bits/stdc++.h>
using namespace std;
int a[5][5];
int zhi[5];
int zuo[5];
int you[5];
int t;
int ans;
int cal(int a ,int b ,int c ,int d)
{
    return max( abs(a)+abs(d)   , abs(b)+abs(c)     );
} 
int main()
{
    cin>>t;
    while(t--)
    {

        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
                cin>>a[i][j];
        for(int i=2;i<=4;i++)
            you[i]=a[i][i-1];
        you[1]=a[1][4];
        for(int i=1;i<=2;i++)//直行是对位
            zhi[i]=a[i][i+2],zhi[i+2]=a[i+2][i];
        for(int i=1;i<=3;i++)
            zuo[i]=a[i][i+1];
        zuo[4]=a[4][1];
        ans=1e9;
        //接着我选三个斜线,从零开始是为了抽象这三条斜线，不然就要考虑他们的位置关系。
        for(int i=0;i<=100;i++)// 斜线1， 减少i 
            for(int j=0;j<=100;j++)// 斜线2， 减少j 
                for(int k=0;k<=100;k++)// 斜线3， 减少k 
                {
                    ans=min(ans,i+j+k+cal(zhi[1] ,zhi[3]-j ,zuo[1]-k ,zuo[3]-i )+cal(zhi[2]-i ,zhi[4]-k ,zuo[2] ,zuo[4]-j ));//不做第1个 
                    ans=min(ans,i+j+k+cal(zhi[1]-i ,zhi[3]-j ,zuo[1]-k ,zuo[3] )+cal(zhi[2] ,zhi[4]-k ,zuo[2]-i ,zuo[4]-j ));// 不做第2个
                    ans=min(ans,i+j+k+cal(zhi[1]-i ,zhi[3] ,zuo[1]-k ,zuo[3]-j )+cal(zhi[2]-j ,zhi[4]-k ,zuo[2]-i ,zuo[4] ));// 不做第3个
                    ans=min(ans,i+j+k+cal(zhi[1]-i ,zhi[3]-k ,zuo[1] ,zuo[3]-j )+cal(zhi[2]-j ,zhi[4] ,zuo[2]-i ,zuo[4]-k ));// 不做第4个
                }
        for(int i=1;i<=4;i++)
            ans=max(ans,you[i]);//右转的特别处理
        cout<<ans<<endl;
    }

}

写在最后：重新定义有手就行(笑)