pat 1044 自己写的暴力解,俩个case超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 1000000000;
struct Pa
{
int begin , end;
};
vector<int> list;
vector<Pa> pairs;
int sum = 0;
Pa p;
void make(int m)
{
int i , j;
sum = 0;
for(i =1 ; i < list.size() ; ++i)
{
for(j = i ; j < list.size() ; ++j)
{
sum += list[j];
if(sum == m)
{
p.begin = i;
p.end = j;
pairs.push_back(p);
break;
}
else if(sum > m)
{
break;
}
}
sum = 0;
}
for(i = 0 ; i < pairs.size() ; ++i)
{
printf("%d-%d\n" , pairs[i].begin , pairs[i].end);
}
}
int main()
{
int n , m;
scanf("%d%d" , &n , &m);
int i,j;
int mem;
list.push_back(-1);
for(i = 0 ; i < n ; ++i)
{
scanf("%d" , &mem);
list.push_back(mem);
}
//3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13
//int sum =0 , begin = 1 , end;
/*for(i = 2 ; i <list.size() ; ++i)
{
if(sum < m)
{
sum += list[i];
}
else if(sum == m)
{
end = i-1;
p.begin = begin;
p.end = end;
pairs.push_back(p);
begin = i;
sum = list[begin];
}
else
{
sum = list[i];
begin = i;
}
}*/
make(m);
if(pairs.size() == 0)
{
int min = INF , mb = 0;
for(i =1 ; i < list.size() ; ++i)
{
for(j = i ; j < list.size() ; ++j)
{
sum += list[j];
if(sum > m)
{
int c = sum - m;
if(c < min)
{
min = c;
mb = sum;
}
else
break;
}
/* if(sum == m)
{
p.begin = i;
p.end = j;
pairs.push_back(p);
break;
}
else if(sum > m)
{
break;
}
*/ }
sum = 0;
}
make(mb);
}
return 0;
}

热评文章