Trại hè 2019 miền trung

nguyenhieuckt · July 23, 2019, 9:41am

E xin trình bày tư tưởng bài này:
Mỗi lần nhập giá trị a[i].x , nếu là đầu mút trái thì a[i].y=1, còn phải thì a[i].y=2.
Sau đó em sort theo a[i].x.
Từ đây em duyện mảng 2*n. Nếu gặp a[i].y =1 thì cho biến đếm++. Nếu a[i].y=2 thì đếm–.
Nếu đếm > kết quả và đếm >1 thì ta lưu kết quả = max(kết quả,đếm)
Em nộp bài 0 điểm và không biết lí do, mong mn giúp đỡ.
Code:

#include <bits/stdc++.h>

using namespace std;
const int maxn=2e6+5;
struct sapxep{
  int x,y;
 };
 sapxep a[maxn];
 bool ss(sapxep q,sapxep p){
   if(q.x==p.x) return q.y>p.y;
   return q.x<p.x;
 }
int n,ans=0,s=0;
int main(){
  //freopen("INSEG.inp","r",stdin);
  //freopen("INSEG.out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n*2;i++)
  {
      scanf("%d",&a[i].x);
      a[i].y=1;
      scanf("%d",&a[++i].x);
      a[i].y=2;
  }
  sort(a+1,a+n*2+1,ss);
  for(int i=1;i<=2*n;i++){
     if(a[i].y==1) s++;
     else if(a[i].y==2) s--;
     if(s>ans && s>1) ans=s;
  }
  printf("%d",ans);
}

Shiharoku · July 23, 2019, 10:13am

Mình chấm thì bạn cũng đáng 0đ á.

Ns vui vậy thôi. Cách làm của bạn quá cồng kềnh, tốn Ram, hao time.

Bạn xây dựng struct gần như để cúng.
Hàm ss() thì mình chả biết nó dùng để làm gì.
Mà lúc gọi hàm này thì bạn còn không thêm tham số cho nó nữa.
```
sort(a+1,a+n*2+1,ss);  // here
```
Cũng chả biết bạn sort() để làm gì luôn.

Nếu suy nghĩ cẩn thận thì bạn có thể để ý đối tượng cần xử lý ở đây là những đoạn thẳng gồm điểm đầu (a) và điểm cuối (b).

Vậy mình xây dựng struct line

struct line {
	int a;
	int b;
};

Tiếp đến đề hỏi có bao nhiêu cạnh giao nhau trong tập các đoạn thẳng đã nhập vào.

Thế là chúng ta lại phải suy nghĩ tiếp làm thế nào để biết được hai đoạn thẳng là giao nhau. xây dựng hàm kiểm tra hai đoạn có giao nhau hay không.

Và đây là hàm checkIntersect() của mình

bool checkIntersect(line x, line y) {
	if (x.a <= y.b && x.b >= y.a)
		return true;
	return false;
}

Sao lại như thì mình không giải thích (bạn lấy giấy ra vẽ thì biết )

Công việc đến đây thì cũng coi như là xong rồi. Chỉ việc kiểm tra từng cặp cạnh trong tập U đề cho với nhau nữa là song.

Và đây là code hoàn chỉnh của mình

Code

#include <iostream>

struct line {
	int a;
	int b;
};

bool checkIntersect(line x, line y) {
	if (x.a <= y.b && x.b >= y.a)
		return true;
	return false;
}

int main() {
	int n = 0;
	std::cin >> n;
	line *u = new line[n];
	int count = 0;

	for (int i = 0; i < n; i++)
		std::cin >> u[i].a >> u[i].b;

	for (int i = 0; i < n - 1; i++)
		for (int j = i + 1; j < n; j++)
			if (checkIntersect(u[i], u[j]))
				count++;
	delete[] u;

	std::cout << count;
	return 0;
}

nguyenhieuckt · July 23, 2019, 11:01am

Hàm struct với ss để mình sort giá trị y theo giá trị x á bạn

Shiharoku · July 23, 2019, 11:46am

Ý chết, xin lỗi mình đọc nhầm đề.

Nhưng mình vẫn không hiểu bạn sort để làm gì. Với lại bạn test + debug case này để biết mình sai ở đâu nha.

3
1 2
1 2
1 2

Sửa lại bài của mình chút xíu. (Cho bạn nào cần thôi)

Edit

#include <iostream>

#define M 2*(int)10e6

int main() {
	int *a = new int[M];
	for (int i = 0; i < M; i++)
		a[i] = 0;
	int n = 0;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		int x = 0, y = 0;
		std::cin >> x >> y;
		for (int j = x; j <= y; j++)
			a[j]++;
	}
	int iMax = 0;
	for (int i = 1; i < M; i++)
		if (a[iMax] < a[i])
			iMax = i;
	if (a[iMax] < 2)
		std::cout << 0;
	else
		std::cout << a[iMax];

	delete[] a;
	return 0;
}

SITUVN.gcd · July 23, 2019, 1:16pm

Mình cũng nghĩ thế.

Nhưng lặp cứng cho a 2*10e6 * 2 - 1 (4000000 - 1) lần có vẻ hơi “lãng phí” nếu chỉ nhập các giá trị nhỏ nhỉ.

Shiharoku · July 23, 2019, 1:44pm

Chắc hơi thừa phần nhân đôi, nhưng đề nó kêu 10^-6 ⩽ a_i ⩽ b_i ⩽ 10⁶.

nguyenhieuckt · July 23, 2019, 2:52pm

Cách của bạn chỉ được 50/100 điểm trong khi cách mình được 65/100 điểm :((

Shiharoku · July 23, 2019, 3:49pm

Bạn chấm điểm ở đâu z.