蒟蒻求助,为什么我的sort有点问题(debug在注释)

P1025 [NOIP2001 提高组] 数的划分

您的代码: ``` sort(d,d+k); ``` 直接在原始数组上排序,会使得递归过程中的赋值发生混乱,从而导致出现问题,正确的做法是使用另外一个数组,复制值然后再排序。例如: ``` #include<bits/stdc++.h> using namespace std; string vis; int d[256], dd[256]; int n,k; int ans; int dg(int x,int cnt) { if(x == k && cnt == n) { string s = ""; memcpy(dd, d, sizeof d); sort(dd,dd+k); for(int i = 0;i<k;i++) { // cout << d[i]; s += to_string(dd[i]); } // cout << '\n'; if(vis.find(s) == string::npos) { vis += s+"\n"; ans++; return 0; } return 0; } if(cnt > n || x > k) { return 0; } for(int i = 1;i<n;i++) { d[x] = i; dg(x+1,cnt+i); } return 0; } int main() { cin >> n >> k; dg(0,0); // int len = vis.size(); // for(int i = 0;i<len;i++) // { // cout << vis[i]; // } cout << ans << '\n'; return 0; } ``` 但是这样做效率不高,会TLE,需要控制枚举的数的顺序,保证以不递减序枚举,这样可以免去排序,从而保证拆分结果的唯一性。
by metaphysis @ 2023-06-13 10:32:38


|