hướng giải
1.sắp xếp hai day tăng dần
2.cho i=0 đến cuối dãy b
j=n-1 đến đầu dãy c
nếu b[i]+c[j]>0
j--;
else
i++
Mình post đề số 1 của đề thi tin học quốc gia 2008 để mọi người làm cho vui nhá.
Cho 2 dãy
b1 b2...bn
c1 c2...cn
tìm min(|bi+cj|)?
input:là 1 số n duy nhất (n<=10^5)
output:giá trị nhỏ nhất tìm được.
lưu ý:các thuật toán độ phức tạp O(n^2) là không khả thi.
hướng giải
1.sắp xếp hai day tăng dần
2.cho i=0 đến cuối dãy b
j=n-1 đến đầu dãy c
nếu b[i]+c[j]>0
j--;
else
i++
cái độ phức tạp được đánh giá từ đây đấy. :-"1.sắp xếp hai day tăng dần
code ra gió bão
Bài này các bạn chú ý một tẹo là giải rất dễ dàng
Với a thuộc dãy 1, b thuộc dãy 2 ta thấy |a+b| bằng một trong các giá trị sau:
1. -a-b
2. -a+b
3. a-b
4. a+b
TH1 và 4: tìm 2 số âm nhỏ nhất hoặc 2 số dương lớn nhất (mỗi số thuộc 1 dãy)
TH2 và 3: tìm a dương lớn nhất, b âm nhỏ nhất hoặc a âm nhỏ nhất b dương lớn nhất.
Giải thuật này có độ phức tạp O(n), mình vừa đọc qua nên giải thuật có khi còn thiếu sót, các bạn bỏ quá.
?
sai lầm chăng?
|a+b| có bao h bằng -a+b hay a-b đâu.
|a+b| chỉ có thể có a+b hoặc a+b.
Mà thuật toán cũng sai. Bạn nên kiểm tra lại.
Thuật toán của mình là áp dụng con trỏ với cây nhị phân tìm kiếm.
-Chọn dãy B là dãy tìm kiếm:
+ta duyệt dãy để tạo cây nhịn phân tìm kiếm.
*độ phức tạp < O(n^2)
- Duyệt dãy A.
+với phần tử A[i] đc duyệt.
+ chú ý |a+b| ( a là hằng số ) nhỏ nhất khi b gần -a nhất.
+ Tìm trong cây nhị phân tìm kiếm giá trị gần -A[i] nhất.
+ tính |a+b| và so sánh với min và cập nhật giá trị Min.
*độ phức tạp < O(n^2)
-> In ra min
hok bít thế này có đc hok
không biết mình có hiểu sai không nhỉ, bài này cứ duyệt cả 2 dãy từ đầu đến cuối cộng chúng lại với nhau rồi chọn thằng nhỏ nhất là OK mà độ phức tạp của nó n*n như code của mình, anh em xem có sai không hộ cái
thanks
Code:// Test1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include<stdio.h> #include<conio.h> #include<math.h> #define MAX 100000 long n,I,J; float a[MAX],b[MAX],result; float A,B; //----------------------- void Input(){ long i; for(i=0;i<MAX;i++){ a[i]=0; b[i]=0; } printf("N="); scanf("%d",&n); result=0; for(i=0;i<n;i++){ printf("a[%d]",i); scanf("%f",&a[i]); } printf("------------------------\n"); for(i=0;i<n;i++){ printf("b[%d]",i); scanf("%f",&b[i]); } result=abs(a[0]+b[0]); A=a[0]; I=0; B=b[0]; J=0; } //-------------------------- float GetResult(){ long i,j; for(i=0;i<n;i++) for(j=0;j<n;j++){ if(abs(a[i]+b[j])<result){ result=abs(a[i]+b[j]); A=a[i]; I=i; B=b[i]; J=j; } } return result; } void main() { Input(); float result=GetResult(); printf("%f+ %f =%f",A,B,result); printf("\n"); printf("a[%d]+ b[%d]",I,J); getch(); }
Time
Vấn đề ở đây là độ phức tạp phải nhỏ hơn n^2, chứ làm thế kia thì chắc chắn được 0 điểm :P.
Is the moon rising...
Đã được chỉnh sửa lần cuối bởi nthung : 04-11-2008 lúc 06:08 PM.
Time
Bài này làm chỉ O(nlogn) thôi. Em mang đi chấm trên vn.spoj.pl accept đc 100% test. Code hơi xấu tẹo tại em gõ ẩu :P
Code:#include<stdio.h> #include<stdlib.h> long n, b[100100],c[100100]; void nhap(); void sort_b(long l,long r); void sort_c(long l,long r); int main() { nhap(); sort_b(0,n-1); sort_c(0,n-1); //xu ly long kq,i,j; kq=abs(b[0]+c[0]); i=0; j=n-1; while(i<=(n-1) && j>=0) { if(kq>abs(b[i]+c[j])) kq=abs(b[i]+c[j]); if((b[i]+c[j])>=0) j--; else i++; } printf("%ld\n",kq); return 0; } void nhap() { long i; scanf("%ld",&n); for(i=0;i<n;i++) scanf("%ld",&b[i]); for(i=0;i<n;i++) scanf("%ld",&c[i]); } void sort_b(long l,long r) { long i,j,x,tmp; i=l; j=r; x=b[(l+r)/2]; do { while(b[i]<x) i++; while(x<b[j]) j--; if(i<=j) { tmp=b[i]; b[i]=b[j]; b[j]=tmp; i++;j--; } } while(i<=j); if(i<r) sort_b(i,r); if(l<j) sort_b(l,j); } void sort_c(long l,long r) { long i,j,x,tmp; i=l;j=r; x=c[(l+r)/2]; do { while(c[i]<x) i++; while(x<c[j]) j--; if(i<=j) { tmp=c[i];c[i]=c[j];c[j]=tmp; i++;j--; } } while(i<=j); if(l<j) sort_c(l,j); if(i<r) sort_c(i,r); }
Đã được chỉnh sửa lần cuối bởi granjota : 04-11-2008 lúc 09:23 PM.