刷题记录

风口的猪-中国牛市

题目描述

风口之下,猪都能飞。当今中国股市牛市,真可谓“错过等七年”。 给你一个回顾历史的机会,已知一支股票连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该股票第i天的股价。 假设你一开始没有股票,但有至多两次买入1股而后卖出1股的机会,并且买入前一定要先保证手上没有股票。若两次交易机会都放弃,收益为0。 设计算法,计算你能获得的最大收益。 输入数值范围:2<=n<=100,0<=prices[i]<=100
输入例子:

3,8,5,1,7,8

输出例子:

12

解题方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int first=0;
int second=0;
int max=0;
for(int i=0;i<prices.size();i++){
for(int j=i;j<prices.size();j++){
first=prices[j]-prices[i];
if(j==prices.size()-1){
second=0;
if(first+second>max)
max=first+second;
continue;
}else{
for(int p=j+1;p<prices.size();p++){
for(int q=p;q<prices.size();q++){
second=prices[q]-prices[p];
if(first+second>max)
max=first+second;
}
}
}
}
}
return max;
}
};

微软机试题

第一题 Queen Attack

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

There are N queens in an infinite chessboard. We say two queens may attack each other if they are in the same vertical line, horizontal line or diagonal line even if there are other queens sitting between them.

Now given the positions of the queens, find out how many pairs may attack each other?

输入

The first line contains an integer N.

Then N lines follow. Each line contains 2 integers Ri and Ci indicating there is a queen in the Ri-th row and Ci-th column.

No two queens share the same position.

For 80% of the data, 1 <= N <= 1000

For 100% of the data, 1 <= N <= 100000, 0 <= Ri, Ci <= 1000000000

输出

One integer, the number of pairs may attack each other.

样例输入

1
2
3
4
5
6
5
1 1
2 2
3 3
1 3
3 1

样例输出

1
10

我的提交

TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//
// Created by matianqi on 2017/4/8.
// 比对当前点和剩下点是否在垂直,水平,斜线上,
// 如果在 res++
using namespace std;
long solution1(long a[] ,long b[],int n){
int res=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]==a[j]||b[i]==b[j]){
res++;
}
else if(abs(a[i]-a[j])==abs(b[i]-b[j])){
res++;
}
}
}
return res;
}
int main(){
int n;
long a[100000];
long b[100000];
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
cout<<solution1(a,b,n)<<endl;
return 0;
}

更好的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
// Created by matianqi on 2017/4/10.
// 统计垂直、水平、斜率为1、斜率为-1的key-value结构,对于每个key,求其value的C(n,2)
#include <iostream>
#include <map>
using namespace std;
int solotion(map<long,int>m1,map<long,int>m2,map<long,int>m3,map<long,int>m4){
int res=0;
for(auto kv:m1){
res+=kv.second*(kv.second-1)/2;
}
for(auto kv:m2){
res+=kv.second*(kv.second-1)/2;
}
for(auto kv:m3){
res+=kv.second*(kv.second-1)/2;
}
for(auto kv:m4){
res+=kv.second*(kv.second-1)/2;
}
return res;
}
int main(){
map<long ,int> m1;
map<long ,int> m2;
map<long ,int> m3;
map<long ,int> m4;
int n;
int a,b;
cin>>n;
for(int i=0;i<n;i++){
cin>>a>>b;
m1[a]++;
m2[b]++;
m3[a-b]++;
m4[a+b]++;
}
cout<<solotion(m1,m2,m3,m4)<<endl;
return 0;
}

第二题 Diligent Robots

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

There are N jobs to be finished. It takes a robot 1 hour to finish one job.

At the beginning you have only one robot. Luckily a robot may build more robots identical to itself. It takes a robot Q hours to build another robot.

So what is the minimum number of hours to finish N jobs?

Note two or more robots working on the same job or building the same robot won’t accelerate the progress.

输入

The first line contains 2 integers, N and Q.

For 70% of the data, 1 <= N <= 1000000

For 100% of the data, 1 <= N <= 1000000000000, 1 <= Q <= 1000

输出

The minimum number of hours.

样例输入

1
10 1

样例输出

1
5

我的提交

TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//
// Created by matianqi on 2017/4/8.
//
#include <iostream>
using namespace std;
long resolution(long n,long q){
long min = n;
long m = 1;
int k = 0;
long numR = 1;
while (numR <= n ) {
long time = 0;
numR += 1;
if ( ((numR - 1)&numR) == 0) {
m *= 2;
k += 1;
int tax = (n%numR==0?0:1);
time = k*q + n / numR + tax;
}
else {
long rest = n - (2*m - numR)*q;
int tax = (rest % numR == 0 ? 0:1);
time = (k+1) * q + rest / numR + tax;
}
if (time < min) min = time;
}
return min;
}
int main(){
long n;
long q;
cin>>n>>q;
cout<<resolution(n,q)<<endl;
}