A 略 B 略
C:
先对Ai数列预处理前缀和 然后把Bi的每个都加一次 最终得到的结果为ans[sum]++; 最后如果有一个ans[sum]>=k即满足所有K个条件就输出(注意!!前缀和要进行unique操作!!!因为可能会有+1 -1 +1这种出现
#include <bits/stdc++.h> #include <cstring> #include <iostream> #include <algorithm> #define foror(i,a,b) for(i=a;i<b;i++) #define foror2(i,a,b) for(i=a;i>b;i--) #define EPS 1.0e-6 #define PI acos(-1.0) #define INF 3000000000 #define MOD 1000000009 #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define lson o<<1, l, m #define rson o<<1|1, m+1, r //using ll = long long; //using ull= unsigned long long; //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; typedef long long ll; map<int,int> mp; stack<int> s; int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int n,k; int ans; cin >> n >> k; int a[n+10],b[k+10]; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]=a[i-1]+a[i]; } for(int i=1;i<=k;i++) { scanf("%d",&b[i]); } sort(a+1,a+1+n); int lenth=unique(a+1,a+1+n)-(a+1); for(int i=1;i<=k;i++) { for(int j=1;j<=lenth;j++) { s.push(b[i]]+a[j]); mp[b[i]]+a[j]]++; } } for(int i=0;i<s.size();i++) { if(mp[s[i]>=k) { ans++; mp[s[i]]=0; } } cout<<ans<<endl; return 0; }
D:
二分或者DP
二分：由于要尽可能使每个人拿到距离自己最近的钥匙，我们先把所有人根据位置排序，把所有钥匙根据位置排序，然后二分答案，判断某一个值是否满足条件，具体判断过程见代码，每次尽量取左边的钥匙。
#include <cstdio> #include <map> #include <iostream> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define rush() int T;scanf("%d",&T);while(T--) typedef long long ll; const int maxn= 2005; const int mod = 20090717; const int INF = 0x3f3f3f3f; const double eps = 1e-6; int n,k,p; ll a[maxn]; ll b[maxn]; bool vis[maxn]; bool judge(ll limit) { int num=0; mst(vis,0); for(int i=0;i<k;i++) for(int j=0;j<n;j++) { if(vis[j]) continue; if(abs(b[i]-a[j])+abs(b[i]-p)<=limit) { vis[j]=true; num++; break; } } return num==n; } int main() { scanf("%d%d%d",&n,&k,&p); for(int i=0;i<n;i++) { scanf("%I64d",&a[i]); } for(int i=0;i<k;i++) { scanf("%I64d",&b[i]); } sort(a,a+n); sort(b,b+k); ll l=0,r=2e9+5; ll ans; while(l<=r) { ll m=(l+r)/2; if(judge(m)) { r=m-1; ans=m; } else l=m+1; } printf("%I64d ",ans); return 0; }
DP：
用dp[i][j]表示前i个人在前j把钥匙中都拿到了钥匙并到达公司的最短时间。(所有人最短时间里的最大值)
可以写出状态转移方程：dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1]+abs(pos[j]-p))) 最终结果便是dp[n][k].
#include <cstdio> #include <map> #include <iostream> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define rush() int T;scanf("%I64d",&T);while(T--) typedef long long ll; const int maxn= 2005; const int mod = 20090717; const ll INF = 1e15; const double eps = 1e-6; int n,k; ll p; ll a[maxn]; ll b[maxn]; ll dp[maxn][maxn]; int main() { scanf("%d%d%I64d",&n,&k,&p); for(int i=1;i<=n;i++) { scanf("%I64d",&a[i]); } for(int i=1;i<=k;i++) { scanf("%I64d",&b[i]); } sort(a+1,a+1+n); sort(b+1,b+1+k); mst(dp,0); for(int i=1;i<=n;i++) for(int j=i;j<=k;j++) { if(i==j) dp[i][j]=max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-p)); //由j>=i，故i==j时特判 else dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-p))); } printf("%I64d ",dp[n][k]); return 0; }