PTA A_1044 Shopping in Mars

798236606

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

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

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. int dia[100010];
   
5. int min = INT_MAX;
   
6. 
   
7. int exact_pay(int n, int price)
   
8. {
   
9.         int i, j, total, flag = 1;
   
10.         
    
11.         for (i = 1; i <= n; i++)
    
12.         {
    
13.                 for (total = dia[j = i]; j <= n; total += dia[++j])
    
14.                 {
    
15.                         if (total == price)
    
16.                         {
    
17.                                 printf("%d-%d\n", i, j);
    
18.                                 
    
19.                                 flag = 0;
    
20.                                 break;
    
21.                         }
    
22.                         
    
23.                         if (total > price)
    
24.                         {
    
25.                                 if (total < min)
    
26.                                         min = total;
    
27. 
    
28.                                 break;
    
29.                         }
    
30.                 }
    
31.         }
    
32.         
    
33.         return flag;
    
34. }
    
35. 
    
36. void min_pay(int n, int price)
    
37. {
    
38.         int i, j, total;
    
39.         
    
40.         for (i = 1; i <= n; i++)
    
41.         {
    
42.                 for (total = dia[j = i]; j <= n; total += dia[++j])
    
43.                 {
    
44.                         if (total == min)
    
45.                         {
    
46.                                 printf("%d-%d\n", i, j);
    
47.                                 break;
    
48.                         }
    
49.                 }
    
50.         }
    
51. }
    
52. 
    
53. int main(void)
    
54. {
    
55.         int n, price, i;
    
56.         
    
57.         scanf("%d %d", &n, &price);
    
58.         
    
59.         for (i = 1; i <= n; i++)
    
60.                 scanf("%d", dia + i);
    
61.                
    
62.         if (exact_pay(n, price))
    
63.                 min_pay(n, price);
    
64. 
    
65.         return 0;
    
66. }

复制代码

2.采用二分法

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. int dia[100010] = {0};
   
5. int min = INT_MAX;
   
6. 
   
7. int binary_search(int left, int right, int price)
   
8. {
   
9.         int i = left, mid, sum;
   
10.         
    
11.         while (left < right)
    
12.         {
    
13.                 mid = (right + left) / 2;
    
14.                 sum = dia[mid] - dia[i - 1];//i~j的和 = dia[j] - dia[i - 1]
    
15. 
    
16.                 if (sum >= price)
    
17.                         right = mid;
    
18.                 else
    
19.                         left = mid + 1;
    
20.         }
    
21.         
    
22.         return left;
    
23. }
    
24. 
    
25. int exact_pay(int n, int price)
    
26. {
    
27.         int i, j, sum, flag = 1;
    
28.    
    
29.         for (i = 1; i <= n; i++)
    
30.         {
    
31.                 j = binary_search(i, n, price);
    
32.                 sum = dia[j] - dia[i - 1];
    
33.                
    
34.                 if (sum == price)
    
35.                 {
    
36.                         printf("%d-%d\n", i, j);
    
37.                         flag = 0;
    
38.                 }
    
39. 
    
40.                 if (sum < min && sum > price)
    
41.                         min = sum;                        
    
42.         }
    
43.    
    
44.         return flag;
    
45. }
    
46. 
    
47. void min_pay(int n)
    
48. {
    
49.         int i, j, sum;
    
50.    
    
51.         for (i = 1; i <= n; i++)
    
52.         {
    
53.                 j = binary_search(i, n, min);
    
54.                 sum = dia[j] - dia[i - 1];
    
55.                
    
56.                 if (sum == min)
    
57.                         printf("%d-%d\n", i, j);
    
58.         }
    
59. }
    
60. 
    
61. 
    
62. int main(void)
    
63. {
    
64.         int n, price, i;
    
65.         
    
66.         scanf("%d %d", &n, &price);
    
67.         
    
68.         for (i = 1; i <= n; i++)
    
69.                 scanf("%d", dia + i);
    
70.                
    
71.         //计算和值        令dia[i] = dia[1]~dia[i]的和
    
72.         for (i = 2; i <= n; i++)
    
73.                 dia[i] += dia[i - 1];
    
74. 
    
75.         if (exact_pay(n, price))
    
76.                 min_pay(n);        
    
77. 
    
78.         return 0;
    
79. }

复制代码