這道題陣列開小了會WA，建議開3e3+10;
題目
Sample Input
1 1
1
1
1 2
2
1 3
Sample Output
1
0
思想與解釋
這道題告訴你東西南北兩個垂直的道路上，有兩列單向行駛的車流（比如東向西，北向南），給你東西方向的車子數量n，南北車子的數量n，下面兩行分別是n個資料和m個資料，標記著a[i]和b[i]時刻有車子，
而且南北車子必須讓著東西方向的車子（也就是說如果出現東西方向1時刻有車，南北方向1時刻也有車，那么東西先開，南北方向的等待一分鐘），題目問的就是兩個方向的車子全部通過路口需要等待的總時間，
我們來思考一下，什么時候兩個方向的車子都可以通過呢？也就是南北車子可以順利通過，不受到東西方向車子的限制（可以理解成不被堵住），那么總是存在某個時刻，使得b所有的車子都能順利通過，輸出此時的等待的時間，
AC代碼
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pre(i,a,b) for(int i=a;i>=b;--i)
#define debug(a) cout << " " << a << " " << endl
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m(x) memset(x,0,sizeof x)
//i可能會會比較大，所以陣列開大一點
const int maxn = 2010;
int a[maxn],b[maxn];
int main(){
int n,m;
while(~scanf("%d%d",&n,&m))
{
m(a);
m(b);
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
a[x] = 1;
}
for(int i=0;i<m;++i)scanf("%d",&b[i]);
int i = 0;
//時間暴力遍歷，總會有一個等待時間使得所有南北方向的車子等待恰當的時間并且不和東西方向的車子撞車
while(1)
{
int flag = 0;
for(int j=0;j<m;j++)
//b[j]+i表示前面等的時間加上b[j]時刻的時間這個時刻是否有東西方向的車，如果有的話說明仍然不成立
if(a[b[j]+i]==1){flag=1;break;}
if(!flag)break;
i++;
}
printf("%d\n",i);
}
return 0;
}
這里需要注意的是陣列需要開多大的情況，我們考慮一個極端情況，如果n=m=1000，且a為1-1000，b與a相同，則此時說明南北方向每輛車都得等a全部開過才能正常通過，那么a陣列就至少得開2e3+10，(實測鋌而走險開2e3也能過，看來資料就是去了1e3以內)
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/275033.html
標籤：其他
上一篇：初學c語言