大二暑假第一周算法题

你可以选择一个奇数和一个偶数，使他们的和尽可能的大，但是要小于nn。
请问他们的和最大为多少。
奇数：不是二的倍数。
偶数：二的倍数。
输入描述:
输入一个正整数nn，4\leq n\leq 10^94≤n≤10 
9
输出描述:
输出一个整数代表答案。
示例1
输入4
输出3
说明：
可以选择11和22
他们的和为33并且3<43<4。

1.题目要求之和最大，并且要求小于当前的这个数，分析一下，偶数只能分成两个偶数或 
者两个奇数，而技术只能分成一个奇数，一个偶数，而题目又有要求分成的两个数，一个奇数一个偶数，那 
答案不就直接出来了，如果输入的是偶数，则答案直接是此数减一；如果输入的是奇数，则答案是次数减 
二；
2.可以让这个数直接除以二，得到的那个数就是答案中的偶数，奇数就是偶数减一，因为要是加一个话得到 
的值就会大于原来的那个数。

#include <iostream>
using namespace std;
int main()
{
int a;
cin>>a;
if(a%2==0)
{
cout<<a-1<<endl;
}
if(a%2!=0)
{
cout<<a-2<<endl;
}
return 0;
}

#include <iostream>
using namespace std;
int main()
{
int a;
cin>>a;
int b=a/2;
int c=b+b-1;
cout<<c<<endl;
return 0;
}

首先分析题目，数组中有0，要把零变成任意正整数，并且保证，最后数组的和最小。
所以我们只需要遍历一遍，碰见0，就把0变成比前一项大一就行了，这样就能保证，它最后的和是最小的
要注意的是，当第一项为0时，要手动变为1。
如果碰见前一项大于后一项的就返回-1，如果没有就加上它；
最后输出就可以了。

#include <iostream>
using namespace std;
int arr[101];
int n;
int main()
{
int count=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
if(arr[0]==0)
{
    arr[0]=1;
}
count+=arr[0];
for(int i=1;i<n;i++)
{
if(arr[i]==0)
    {
        arr[i]=arr[i-1]+1;
    }else{
if(arr[i]<=arr[i-1])
        {
cout<<-1<<endl;
return 0;
        }
    }
    count+=arr[i];
}
cout<<count<<endl;
return 0;
}

这道题呢，有一点点“小南”，题目说最后x是偶数，并且x的值是输入进去的，注意一下，第一，他们一次 
消去的是相同的两个数，并且是相邻的，如果原本长度是奇数，那么就不可能到最后是偶数；第二，如果 
给定的0、1个数还没有最后指定留下来的多，那么也不可能；第三，如果前两个满足的话，你还要判断一 
下，他们的长度减去要求留下的x/2之后，他们是不是偶数，如果不是那么同时不可能经过n次消除，能消 
除完，剩要保留的个数。

#include <iostream>
using namespace std;
int main()
{
int a,b,x;
cin>>a>>b>>x;
x=x/2;
if((a+b)&1||a<x||b<x)
{
cout<<-1<<endl;
return 0;
}
a=a-x;
b=b-x;
if(a&1||b&1)
{
cout<<-1<<endl;
return 0;
}
for(int i=0;i<a;i++)cout<<"0";
for(int i=0;i<b;i++)cout<<"1";
for(int i=0;i<x;i++)cout<<"01";
return 0;
}

这道题不难，但是我还是花了很长时间，思路很简单，第一步判断输入的长度是不是大于等于26，小于的 话直接输出NO；第二步就是大小写统一；第三步用map函数存值，key为字母，value为出现的次数，map函数的特点就是，碰见map中没有的直接存进去，并且value+1，如果有 value直接+1；难点就在于我这些函数不熟悉。

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
if(n<26&&n>0)
{
cout<<"NO"<<endl;
return 0;
}
string s;
cin>>s;
map<char , int> mp;
for(int i=0;i<n;i++)
{
if(s[i]>=65&&s[i]<=90)
    {
        s[i]=tolower(s[i]);
    }
}
for(int i=0;i<n;i++)
{
    mp[s[i]]++;
}
if(mp.size()==26)
{
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}

这道题是很简单的，题目已经把规律给得很清楚了，创建一个新的数组，这个数组的长度是原数组的一半，每次你处理的时候乘以2就可以了，再判断一下，当前是第几个数对分一下是求最小值还是最大值，最后把这个数组赋值给原数组，再次进入循环，直到长度为1时，退出循环即可。最后输出为一个一个元素，即是答案。

#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> nums={1,3,5,2,4,8,2,2}; 
（这个是我在本地调试的时候直接放数据了）
while(nums.size()>1)（判断条件）
{
vector<int> num(nums.size()/2,0);（每次创建一个新数组）
for(int i=0;i<nums.size()/2;i++)
    {
if(i%2==0)
        {
            num[i]=min(nums[i*2],nums[i*2+1]);
        }else{
            num[i]=max(nums[i*2],nums[i*2+1]);
        }
    }
    nums=num;
}
cout<<nums[0]<<endl;
return 0;
}

这道题就有点小绕脑子了，这道题的简单之处在于没有让你那最后的结果输出出来，只用输出有几个数组满足条件就行了。简单分析一下，它说了那么多，无非就是，求这个数组可以分为几个长度为k的子数组，本人再看这道题时，想复杂了，用来map函数，但其实不用这么复杂，
很显然，一眼贪心。因为能凑成一组的尽可能地都塞进一组中，这样是更优的。
从最大值来看，对于全局最大值 max，我一定会让所有在 [max−k,max] 之间的值分为一组。

class Solution {
public:
int partitionArray(vector<int>& nums, int k) {
    sort(nums.begin(),nums.end());
int n=nums.size();
int count=1;
int a=nums[0],b=0;（记录一下最小值，另外定义一个中间变量）
for(int i=0;i<n;i++)
    {
if(nums[i]-a<=k) continue;（差值在k之间的不用管）
else{ （如果不在，则要变一下当前最小值，记录一下值）
            a=nums[i];
            count++;
        }
    }
return count;
}
};