笔试DAY4

admin管理员组

文章数量:823559

笔试DAY4

鸡鸭分类（类双指针）

题目描述：
农场有n只鸡鸭排为一个队伍，鸡用“C”表示，鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整，使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻，需要调整队形两次。

输入描述:
输入一个长度为N，且只包含C和D的非空字符串。
输出描述:
使得最后仅有一对鸡鸭相邻，最少的交换次数。

思路：
交换最后得到的结果只有两种，鸡左鸭右，鸭左鸡右
在代码中可以把‘C’都全移到左边或者把‘D’全移到左边，去最小者即可

#include <iostream>
#include <string>using namespace std;int main()
{string s;cin >> s;int count = 0;int sumC = 0;int sumD = 0;// 把C往左移for(int i = 0; i<s.size(); i++){if(s[i] == 'C'){   //单引号sumC += i-count++;  //********}}// 把D往左移count = 0;   //重置for(int i = 0; i < s.size(); i++){if(s[i] == 'D'){sumD += i-count++;   //********}}cout << min(sumC, sumD) << endl;return 0;
}

其中count计数这是第几个c/d（从0开始）i-count为第i个字符需要移动的个数
输入：cin>>“CCDCC”
C左移：
i=0,s[1]=c,sumc=0+0-0;
i=1,s[1]=c,sumc=0+1-1;
i=2,s[2]=d;
i=3,s[3]=c,sumc=0+3-2;
i=4,s[4]=c,sumc=1+4-3=2;
D左移：
i=0,s[1]=c;
i=1,s[1]=c;
i=2,s[2]=d,sumd=0+2-0=2;
i=3,s[3]=c;
i=4,s[4]=c;
输出：cout<<2

比特币最佳买卖时间

题目描述：
给定一个正整数数组，它的第 i 个元素是比特币第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一次），设计一个算法来计算你所能获取的最大利润。注意你不能在买入比特币前卖出。

输入描述:
正整数数组，为以空格分隔的n个正整数
输出描述:
最大利润

C++中cin的详细用法
ctrl+z结束

#include<bits/stdc++.h>
using namespace std;int main() {int n, mi = INT_MAX, maxProfit = 0;while(cin >> n) { //*****maxProfit = max(n - mi, maxProfit);mi = min(n, mi);}cout << maxProfit;return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
public class Main{public static void main(String[] args){Scanner in = new Scanner(System.in);ArrayList<Integer> coin=new ArrayList<>();while(in.hasNextInt()){coin.add(in.nextInt());}Integer[] co=new Integer[coin.size()];coin.toArray(co);int profit=0;for(int i=co.length-1;i>=0;i--)for(int j=0;j<i;j++){profit=Math.max((co[i]-co[j]),profit);}System.out.println(profit);}
}

爱吃喵粮的小猫（贪心）

题目描述：
小招喵喜欢吃喵粮。这里有 N 堆喵粮，第 i 堆中有 p[i] 粒喵粮。喵主人离开了，将在 H 小时后回来。
小招喵可以决定她吃喵粮的速度 K （单位：粒/小时）。每个小时，她将会选择一堆喵粮，从中吃掉 K 粒。如果这堆喵粮少于 K 粒，她将吃掉这堆的所有喵粮，然后这一小时内不会再吃更多的喵粮。

小招喵喜欢慢慢吃，但仍然想在喵主人回来前吃掉所有的喵粮。返回她可以在 H 小时内吃掉所有喵粮的最小速度 K（K 为整数）。

输入描述:
第一行输入为喵粮数组，以空格分隔的N个整数
第二行输入为H小时数
输出描述:
最小速度K

贪心 + 二分查找
理论最小进食速度： 所有喵粮求和 / 给定的小时数
理论最大进食速度：最大堆的喵粮数
在这两个之间二分查找最小实际可行进食速度即可
注：这是一个lower_bound的二分问题，即求最左边满足条件的值 需要相应修改二分查找

#include <bits/stdc++.h>
using namespace std;vector<int> arr;
int H, tmp, sum = 0, res, mmax = 0, mmin; bool solve(int x, int H) {//x为速度int res = 0;//吃完所有猫粮所需时间for(int i = 0; i < arr.size(); i++) {res += (arr[i] % x == 0) ? arr[i] / x: arr[i] / x + 1;}return res <= H;
}int main() {string line; getline(cin, line);istringstream iss(line);while(iss >> tmp) {arr.push_back(tmp);mmax = max(mmax, tmp);sum 

本文标签： 笔试DAY4