#include <iostream>
using namespace std;
int main() {
int n, m, a[10000] = {0}, b[10000] = {0}, count = 0, curr = 0;
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[j];
}
for (int j = 0; j < m; j++){
cin >> b[j];
}
for (int k = 0; k < m; k++){
for (int h = curr; h < m; h++){
if (a[k] == b[h]){
count++;
curr = h+1;
break;
}
if (a[k] < b[h]){
curr = h;
break;
}
}
}
cout << count << "\n";
count = 0;
curr = 0;
}
return 0;
}
我覺得我已經盡量用最快的方法了還是TLE :(
leeguanhan0909@gmail.com
(李冠翰)
學校
:
高雄市苓雅區復華高級中學國中部
編號 : 276558
來源 : [36.238.153.220]
最後登入時間 ：
2025-04-05 17:05:47
#include
using namespace std;
int main() {
int n, m, a[10000] = {0}, b[10000] = {0}, count = 0, curr = 0;
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[j];
}
for (int j = 0; j < m; j++){
cin >> b[j];
}
for (int k = 0; k < m; k++){
for (int h = curr; h < m; h++){
if (a[k] == b[h]){
count++;
curr = h+1;
break;
}
if (a[k] < b[h]){
curr = h;
break;
}
}
}
cout << count << "\n";
count = 0;
curr = 0;
}
return 0;
}
我覺得我已經盡量用最快的方法了還是TLE :(
題目有保證自己不重複，所以可以使用set(#include <set>)，函式庫包含set_intersection（取集合交集）。取得交集的長度即為個數，降低時間複雜度。
#include
using namespace std;
int main() {
int n, m, a[10000] = {0}, b[10000] = {0}, count = 0, curr = 0;
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[j];
}
for (int j = 0; j < m; j++){
cin >> b[j];
}
for (int k = 0; k < m; k++){
for (int h = curr; h < m; h++){
if (a[k] == b[h]){
count++;
curr = h+1;
break;
}
if (a[k] < b[h]){
curr = h;
break;
}
}
}
cout << count << "\n";
count = 0;
curr = 0;
}
return 0;
}
我覺得我已經盡量用最快的方法了還是TLE :(
題目有保證自己不重複，所以可以使用set(#include )，函式庫包含set_intersection（取集合交集）。取得交集的長度即為個數，降低時間複雜度。
我看討論區也有看到這種作法但真的沒辦法用一般的方法嗎？
leeguanhan0909@gmail.com
(李冠翰)
學校
:
高雄市苓雅區復華高級中學國中部
編號 : 276558
來源 : [36.238.153.220]
最後登入時間 ：
2025-04-05 17:05:47
#include
using namespace std;
int main() {
int n, m, a[10000] = {0}, b[10000] = {0}, count = 0, curr = 0;
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[j];
}
for (int j = 0; j < m; j++){
cin >> b[j];
}
for (int k = 0; k < m; k++){
for (int h = curr; h < m; h++){
if (a[k] == b[h]){
count++;
curr = h+1;
break;
}
if (a[k] < b[h]){
curr = h;
break;
}
}
}
cout << count << "\n";
count = 0;
curr = 0;
}
return 0;
}
我覺得我已經盡量用最快的方法了還是TLE :(
題目有保證自己不重複，所以可以使用set(#include )，函式庫包含set_intersection（取集合交集）。取得交集的長度即為個數，降低時間複雜度。
我看討論區也有看到這種作法但真的沒辦法用一般的方法嗎？
感覺很困難，worst case(兩人的幾乎一樣) 每一組就是O(10000^2=1億)，10000組就是(10000^3=1兆)，雖然不一定到如此誇張，但應該不會差太多。用set可以快很多。
#include
using namespace std;
int main() {
int n, m, a[10000] = {0}, b[10000] = {0}, count = 0, curr = 0;
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[j];
}
for (int j = 0; j < m; j++){
cin >> b[j];
}
for (int k = 0; k < m; k++){
for (int h = curr; h < m; h++){
if (a[k] == b[h]){
count++;
curr = h+1;
break;
}
if (a[k] < b[h]){
curr = h;
break;
}
}
}
cout << count << "\n";
count = 0;
curr = 0;
}
return 0;
}
我覺得我已經盡量用最快的方法了還是TLE :(
題目有保證自己不重複，所以可以使用set(#include )，函式庫包含set_intersection（取集合交集）。取得交集的長度即為個數，降低時間複雜度。
我看討論區也有看到這種作法但真的沒辦法用一般的方法嗎？
感覺很困難，worst case(兩人的幾乎一樣) 每一組就是O(10000^2=1億)，10000組就是(10000^3=1兆)，雖然不一定到如此誇張，但應該不會差太多。用set可以快很多。
恩好吧謝謝⚡神