NC51036. The Buses
描述
输入描述
Your program is to read from standard input. The input contains a number telling how many arriving buses have been noted, followed by the arrival times in ascending order.
输出描述
Your program is to write to standard output. The output contains one integer, which is the fewest number of bus routes.
示例1
输入:
17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
输出:
3
C++(g++ 7.5.0) 解法, 执行用时: 16ms, 内存消耗: 440K, 提交时间: 2022-08-02 13:16:36
#include<bits/stdc++.h> using namespace std; const int N=60; struct node { int x,y,z; bool operator <(const node a)const{return z>a.z;} }; vector<node>b; int cnt[65],ans;int n; bool pd(int x,int y) { for(int i=x;i<N;i+=y) if(!cnt[i])return 0; return 1; } void dfs(int x,int now) { if(n<=0) { ans=min(ans,now); return ; } for(int i=x;i<b.size();i++) { if(now+n/b[i].z>=ans)return ; if(pd(b[i].x,b[i].y)) { for(int j=b[i].x;j<N;j+=b[i].y) { --cnt[j]; --n; } dfs(i,now+1); for(int j=b[i].x;j<N;j+=b[i].y) { ++cnt[j]; ++n; } } } } int main() { scanf("%d",&n);memset(cnt,0,sizeof(cnt)); ans=17; for(int i=1;i<=n;i++) { int a;scanf("%d",&a);++cnt[a]; } for(int i=0;i<N/2;i++) for(int j=i+1;j<N-i;j++) { if(cnt[i]) { if(pd(i,j)) { node p; p.x=i,p.y=j;p.z=(N-i-1)/j+1; b.push_back(p); } } } sort(b.begin(),b.end()); dfs(0,0); printf("%d\n",ans); return 0; }
C++ 解法, 执行用时: 11ms, 内存消耗: 384K, 提交时间: 2021-10-06 23:32:09
#include<bits/stdc++.h> using namespace std; int n, a[75], tot; void pre() { cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; a[x]++; } } bool check() { for (int i = 0; i < 60; i++) if (a[i] > 0) return false; return true; } bool valid(int b, int d) { for (int i = 0; b + i * d < 60; i++) if (!a[b + i * d]) return false; return true; } bool dfs(int p) { int b = 0; if (p > tot) return false; while (a[b] == 0 && b < 60) b++; if (b > 30) return false; int flag = 0; for (int gap = 1; gap < 30; gap++) { if (!valid(b, gap)) continue; for (int i = 0; b + i * gap < 60; i++) { a[b + i * gap]--; } if (check()) { flag = 1; } if(dfs(p + 1)) flag = 1; for (int i = 0; b + i * gap < 60; i++) { a[b + i * gap]++; } if (flag) return true; } return false; } int main( ) { pre(); if (n > 50) {cout << 17 << endl;return 0;} int l = 1, r = 17; while (l < r) { tot = (l + r) / 2; if (dfs(1)) r = tot; else l = tot + 1; } cout << l << endl; return 0; }