论坛 › C\C++交流 › PTA A_1044 Shopping in Mars

798236606 发表于 2020-1-28 13:09:29

PTA A_1044 Shopping in Mars

本帖最后由 798236606 于 2020-1-28 13:12 编辑

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

解：
1.暴力枚举， 会有2组数据超时{:10_277:}
#include <stdio.h>
#include <limits.h>

int dia;
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 <= 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 <= 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.采用二分法{:10_256:}
#include <stdio.h>
#include <limits.h>

int dia = {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 - dia;//i~j的和 = dia - dia

                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 - dia;
               
                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 - dia;
               
                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 = dia~dia的和
      for (i = 2; i <= n; i++)
                dia += dia;

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

      return 0;
}

查看完整版本: PTA A_1044 Shopping in Mars