PTA A_1044 Shopping in Mars

798236606

题目连接：https://pintia.cn/problem-sets/994805342720868352/problems/994805439202443264

解：
1.暴力枚举， 会有2组数据超时

#include <stdio.h>
#include <limits.h>

int dia[100010];
int min = INT_MAX;

int exact_pay(int n, int price)
{
        int i, j, total, flag = 1;
        
        for (i = 1; i <= n; i++)
        {
                for (total = dia[j = i]; j <= n; total += dia[++j])
                {
                        if (total == price)
                        {
                                printf("%d-%d\n", i, j);
                                
                                flag = 0;
                                break;
                        }
                        
                        if (total > price)
                        {
                                if (total < min)
                                        min = total;

                                break;
                        }
                }
        }
        
        return flag;
}

void min_pay(int n, int price)
{
        int i, j, total;
        
        for (i = 1; i <= n; i++)
        {
                for (total = dia[j = i]; j <= n; total += dia[++j])
                {
                        if (total == min)
                        {
                                printf("%d-%d\n", i, j);
                                break;
                        }
                }
        }
}

int main(void)
{
        int n, price, i;
        
        scanf("%d %d", &n, &price);
        
        for (i = 1; i <= n; i++)
                scanf("%d", dia + i);
                
        if (exact_pay(n, price))
                min_pay(n, price);

        return 0;
}

2.采用二分法

#include <stdio.h>
#include <limits.h>

int dia[100010] = {0};
int min = INT_MAX;

int binary_search(int left, int right, int price)
{
        int i = left, mid, sum;
        
        while (left < right)
        {
                mid = (right + left) / 2;
                sum = dia[mid] - dia[i - 1];//i~j的和 = dia[j] - dia[i - 1]

                if (sum >= price)
                        right = mid;
                else
                        left = mid + 1;
        }
        
        return left;
}

int exact_pay(int n, int price)
{
        int i, j, sum, flag = 1;
    
        for (i = 1; i <= n; i++)
        {
                j = binary_search(i, n, price);
                sum = dia[j] - dia[i - 1];
                
                if (sum == price)
                {
                        printf("%d-%d\n", i, j);
                        flag = 0;
                }

                if (sum < min && sum > price)
                        min = sum;                        
        }
    
        return flag;
}

void min_pay(int n)
{
        int i, j, sum;
    
        for (i = 1; i <= n; i++)
        {
                j = binary_search(i, n, min);
                sum = dia[j] - dia[i - 1];
                
                if (sum == min)
                        printf("%d-%d\n", i, j);
        }
}


int main(void)
{
        int n, price, i;
        
        scanf("%d %d", &n, &price);
        
        for (i = 1; i <= n; i++)
                scanf("%d", dia + i);
                
        //计算和值        令dia[i] = dia[1]~dia[i]的和 
        for (i = 2; i <= n; i++)
                dia[i] += dia[i - 1];

        if (exact_pay(n, price))
                min_pay(n);        

        return 0;
}