网易2019实习生Java编程题

题1：平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。

思路：把坐标离散化之后直接统计（当时通过率90%）

#include<stdio.h> #include<algorithm> #include<map> using namespace std;int main(){const int N=500;int x1[N],y1[N],x2[N],y2[N],s[N],f[N][N];map<int,int> mp;mp.clear();for (int i=0; i<N; i++)for (int j=0; j<N; j++) f[i][j]=0;int n;scanf("%d",&n);for (int i=0; i<n; i++)scanf("%d",&x1[i]),s[i]=x1[i];for (int i=0; i<n; i++)scanf("%d",&y1[i]),s[n+i]=y1[i];for (int i=0; i<n; i++)scanf("%d",&x2[i]),s[2*n+i]=x2[i];for (int i=0; i<n; i++)scanf("%d",&y2[i]),s[3*n+i]=y2[i];int c=0;sort(s,s+4*n);for (int i=0; i<4*n; i++){if (mp.count(s[i])==0){mp[s[i]]=c++;}}for (int i=0; i<n; i++){if (x1[i]>x2[i]) swap(x1[i],x2[i]);if (y1[i]>y2[i]) swap(y1[i],y2[i]);for (int a=mp[x1[i]]; a<=mp[x2[i]]; a++)for (int b=mp[y1[i]]; b<=mp[y2[i]]; b++) f[a][b]++;}int ans=0;for (int i=0; i<c; i++)for (int j=0; j<c; j++){ans=max(ans,f[i][j]);}printf("%d\n",ans);return 0; }

题2:牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。

思路：枚举y（当心k=0的情况，当时没考虑，80%通过率）

#include <iostream> #include <algorithm> using namespace std;int main() {long long n,k;cin>>n>>k;long long ans=0;for(int y=max(1LL,k);y<=n;++y){int res=0;res=n/y*(y-k);if(n%y>=k)if(k)res+=n%y-k+1;else res+=n%y;ans+=res;}cout<<ans<<endl; }

题3：为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。

思路：简单的背包

#include <stdio.h> #include <algorithm> using namespace std; typedef pair<int,int>pii;const int N=100010;pii dat[N],a[N]; int ans[N];void solve(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d%d",&dat[i].first,&dat[i].second);sort(dat+1,dat+n+1);for(int i=1;i<=m;i++) scanf("%d",&a[i].first),a[i].second=i;sort(a+1,a+m+1);int cur=0;for(int i=1,j=1;j<=m;j++){while(i<=n && dat[i].first<=a[j].first){cur=max(cur,dat[i].second);i++;}ans[a[j].second]=cur;}for(int i=1;i<=m;i++) printf("%d\n",ans[i]); }int main(){solve();return 0; }

总结

以上是生活随笔为你收集整理的网易2019实习生Java编程题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。