acwing.第71场周赛

acwing 4621.三个整数

原题链接：https://www.acwing.com/problem/content/4624/

解题思路

题目保证一定有解,说明给的abcd是一定可以找到答案xyz的

要求x + y > z
让左边取最大值，右边取最小值
即x取b,y取c,z取c
b + c > c恒成立(abcd都大于1已知)

代码

#include<iostream>

using namespace std;

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    
    cout << b << ' ' << c << ' ' << c ;
    
    return 0;
}

acwing 4622.整数拆分

原题链接：https://www.acwing.com/problem/content/4625/

解题思路

f(x)表示除本身之外的最大因数 (x > 2)

哥德巴赫猜想：
任何一个大于等于6的偶数都可以表示成两个素数之和。

如果n为质数，不用拆分，结果为1
如果n为偶数：
	如果n为偶合数：
		n为4，结果为2
		n >= 6，结果为2 (哥德巴赫猜想)
	如果n为奇合数：(1 3 5 7 9，n一定大于等于9)
		如果n-2为质数，就将n拆成(2,n-2)，结果为2
		如果n-2为合数，就将n拆成3和一个偶合数(不可能拆成两个质数，因为两个质数相加还是质数，所以拆出一个3剩下的一定是一个合数)，可以拆成两个素数之和，结果为1 + 2 = 3

代码

#include<iostream>

using namespace std;

int n;

bool is_prime(int x)
{
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0) return false;
    }
    return true;
}

int main()
{
    cin >> n;
    
    if(is_prime(n)) puts("1");
    else if(n % 2 == 0 || is_prime(n - 2)) puts("2");
    else puts("3");
    
    return 0;
}

acwing 4623.买糖果

原题链接：https://www.acwing.com/problem/content/4626/

解题思路

直接暴力模拟，会tle：如果存在每遍历一圈，至少有一个店铺就买不起了，那么时间复杂度可能会\(O(n^2)\)，然而while暴力枚举可能情况会更糟，更tle

暴力枚举+优化：(每次计算出买一圈需要sum钱，买cnt个)

每次遍历一圈n个糖果店，这一次遍历可以计算花费了多少钱，买了多少个糖果
比如计算出来花费了sum钱，买了cnt个糖果。

那么这样的一圈，可以进行T/sum次(购买遍历)，所以可以买T/sum * cnt个糖果，剩下的钱为T%sum。

如果某一圈中有一个糖果店中买不了了，那么在以后所有每次一圈一圈遍历，都是买不了的。

如果某次遍历了一圈，sum = 0，cnt = 0，说明就没有可以买的糖果店了。

关于时间复杂度：这样每次遍历一遍所有糖果店，计算出买一圈要钱sum，可以买cnt个糖果。每遍历一次出sum和cnt结果，都可以直接计算出可以进行T/sum次这样的过程，购买了T/sum * cnt个糖果，剩下T%sum元。那么最坏的情况就是每次有一个糖果店买不起了，看上去时间复杂度还是\(O(n^2)\)，但是实际上，看 T %= sum: sum <= T(每次到T%sum时，恒成立)
1.若sum > T/2: T % sum = T-sum < T/2
2.若sum <= T/2: T%sum < sum <= T/2
因此每次T都会变成原来一般还小，所以总的时间复杂度大概是\(O(nlogn)\)

代码

#include<iostream>

using namespace std;

typedef long long LL;
const int N = 2e5+10;

int a[N];
int n;
LL t,ans;

int main()
{
    scanf("%d%lld",&n,&t);
    
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    while(true)
    {
        LL sum = 0; // 一圈下来如果都取极限值就可能爆int
        int cnt = 0;
        for(int i = 1; i <= n;i ++)
        {
            if(sum + a[i] <= t) // 如果买得起就统计
            {
                sum += a[i];
                cnt ++;
            }
        }
        if(sum == 0) break;
        ans += t/sum * cnt;
        t %= sum;
    }
    
    printf("%lld\n",ans);
    
    return 0;
}