struct m{ int i,j,k; bool operator< (const m & t){ if(i!=t.i) return i<t.i; if(j!=t.j) return j<t.j; return k<t.k; } }m[N]; //进行结构体的比较时,重载运算符规定好规则,然后用sort进行排序 sort(m,m+num);
1221. 四平方和
https://www.acwing.com/problem/content/description/1223/
启发::利用空间换时间、
将四层循环分成两个两层循环,将前面的循环结果进行保存,然后后面的结果进行判断,利用二分取出相应的结果
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N=5000010; struct m{ int i,j,k; bool operator< (const m & t){ if(i!=t.i) return i<t.i; if(j!=t.j) return j<t.j; return k<t.k; } }m[N]; int main() { int n;cin>>n;int num=0; for(int i=0;i*i<=n;i++){ for(int j=i;i*i+j*j<=n;j++){ m[num++]={i*i+j*j,i,j}; } } sort(m,m+num); for(int i=0;i*i<=n;i++){ for(int j=i;j*j+i*i<=n;j++){ int k=n-i*i-j*j; int l=0,r=num; while(l<r){ int mid=l+r>>1; if(m[mid].i>=k) r=mid; else l=mid+1; } if(m[l].i==k){ cout<<i<<" "<<j<<" "<<m[l].j<<" "<<m[l].k<<endl; exit(0); } } } return 0; }
哈希
#include<unordered_map>//引用头文件 #define x first #define y second typedef pair<int, int> PII; unordered_map<int, PII> S; S.count(t) //if t存在返回0 S[t] = {c, d}; if (S.count(t)) { printf("%d %d %d %d\n", a, b, S[t].x, S[t].y); return 0; }
标签:const,补充,mid,蓝桥,int,细节,return,include From: https://www.cnblogs.com/daimazhishen/p/18050598