题目意思是每行给你四个数,然后再每列选一个数,四列任取一组之和等于0,求有多少组这种组合?
一开始想复杂了,以为是动态规划,后来比完才知道是二分,暴力也可以做(不知道为什么暴力时间还短一些)。
暴力的话就是先a、b组合排序,然后c、d组合排序。从ab的开头开始找,从cd的末尾开始找,这样时间会快点。
二分的话就是,排列的的时候将cd组合为-(c+d),然后排序之后二分查找和ab相同的即可。
代码:
Status | Accepted |
---|---|
Time | 4500ms |
Memory | 49168kB |
Length | 846 |
Lang | C++ |
暴力:
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define MAX 4005 int ab[MAX*MAX], cd[MAX*MAX]; int a[MAX], b[MAX], c[MAX], d[MAX]; int n, ans; int main() { while(~scanf("%d", &n)){ for(int i=0;i<n;i++){ scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]); } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ab[i*n+j]=a[i]+b[j]; cd[i*n+j]=c[i]+d[j]; } } sort(ab, ab+n*n); sort(cd, cd+n*n); ans=0; int pos=n*n-1; for(int i=0;i<n*n;i++){ while(ab[i]+cd[pos]>0&&pos>=0)pos--; if(pos<0)break; int t=pos; while(ab[i]+cd[t]==0&&t>=0){ ans++;t--; } } printf("%d\n", ans); } return 0; }
代码:
Status | Accepted |
---|---|
Time | 5610ms |
Memory | 49168kB |
Length | 986 |
Lang | C++ |
二分:
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define MAX 4005 int a[MAX], b[MAX], c[MAX], d[MAX]; int ab[MAX*MAX], cd[MAX*MAX]; int n, ans; int search_num(int x){ int l=0,r=n*n-1,mid; while(l<=r){ mid=(l+r)/2; if(cd[mid]==x){ int cnt=0, pos=mid; while(pos>=0&&cd[pos--]==x)cnt++; pos=mid+1; while(pos<n*n&&cd[pos++]==x)cnt++; return cnt; } else if(cd[mid]<x)l=mid+1; else r=mid-1; } return 0; } int main() { while(~scanf("%d", &n)){ for(int i=0;i<n;i++)scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ab[i*n+j]=a[i]+b[j]; cd[i*n+j]=-(c[i]+d[j]); } } sort(ab, ab+n*n); sort(cd, cd+n*n); for(int i=0;i<n*n;i++)ans+=search_num(ab[i]); printf("%d\n", ans); } return 0; }
-
淡化浅出
2017-05-02 上午 10:51:41
Windows 8.1 x64
UC Browser 6.1.2107.204
-
freeloop
2017-03-16 下午 11:15:58
Windows 7 x64
Google Chrome 50.0.2661.102
-
freeloop
2017-03-16 下午 11:10:41
Windows 7 x64
Google Chrome 50.0.2661.102
计科出身的果然不一样。。。666
-
woodcoding
2017-05-02 下午 06:48:43
Windows 10 x64
Google Chrome 58.0.3029.81
专业研究方向不同而已
不过你这个二分代码常数的确有点大。。。应该lower_search()再upper_search()的。。
-
woodcoding
2017-03-17 下午 07:32:24
Windows 10 x64
Google Chrome 50.0.2661.102
所噶
这个暴力的方法就是双指针呀,我没有想到。。。这个时间复杂度的确更优,因为这样查询的话,两个数组至多扫描完,也就是2*n^2,二分的话复杂度是n^2*logn^2