Topcoder SRM629 DIV2 解题报告

250：乱搞

 1 // BEGIN CUT HERE
 2 /*
 3 
 4 */
 5 // END CUT HERE
 6 #line 7 "RectangleCoveringEasy.cpp"
 7 #include <cstdlib>
 8 #include <cctype>
 9 #include <cstring>
10 #include <cstdio>
11 #include <cmath>
12 #include <algorithm>
13 #include <vector>
14 #include <string>
15 #include <iostream>
16 #include <sstream>
17 #include <map>
18 #include <set>
19 #include <queue>
20 #include <stack>
21 #include <fstream>
22 #include <numeric>
23 #include <iomanip>
24 #include <bitset>
25 #include <list>
26 #include <stdexcept>
27 #include <functional>
28 #include <utility>
29 #include <ctime>
30 using namespace std;
31 
32 #define PB push_back
33 #define MP make_pair
34 
35 #define REP(i,n) for(i=0;i<(n);++i)
36 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
37 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
38 
39 typedef vector<int> VI;
40 typedef vector<string> VS;
41 typedef vector<double> VD;
42 typedef long long LL;
43 typedef pair<int,int> PII;
44 
45 
46 class RectangleCoveringEasy
47 {
48         public:
49         int solve(int a, int b, int c, int d)
50         {
51             if(a > b)
52                 swap(a,b);
53             if(c > d)
54                 swap(a,b);
55             if(c <= a && d <= b )
56                 return -1;
57             if(c > a && d > b)
58                return 1;
59             if(c > a && d == b)
60                 return 1;
61             if(c == a && d > b )
62                 return 1;
63             return -1;
64 
65         }
66         
67 
68 };

View Code

550：本来以为这个绝对值函数是一个单峰函数，就用三分去撸了，结果没撸对，精度不够。

后来才发现绝对值函数都是折线函数，所以只用取端点值就行。

 1 // BEGIN CUT HERE
 2 /*
 3 
 4 */
 5 // END CUT HERE
 6 #line 7 "CandyMaking.cpp"
 7 #include <cstdlib>
 8 #include <cctype>
 9 #include <cstring>
10 #include <cstdio>
11 #include <cmath>
12 #include <algorithm>
13 #include <vector>
14 #include <string>
15 #include <iostream>
16 #include <sstream>
17 #include <map>
18 #include <set>
19 #include <queue>
20 #include <stack>
21 #include <fstream>
22 #include <numeric>
23 #include <iomanip>
24 #include <bitset>
25 #include <list>
26 #include <stdexcept>
27 #include <functional>
28 #include <utility>
29 #include <ctime>
30 #include <unistd.h>
31 using namespace std;
32 
33 #define PB push_back
34 #define MP make_pair
35 
36 #define REP(i,n) for(i=0;i<(n);++i)
37 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
38 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
39 
40 typedef vector<int> VI;
41 typedef vector<string> VS;
42 typedef vector<double> VD;
43 typedef long long LL;
44 typedef pair<int,int> PII;
45 
46 int n;
47 class CandyMaking
48 {
49         public:
50         double solve(double x,vector<int> a, vector <int > b)
51         {
52           double  sum = 0;
53           for(int i = 0 ;i < n ;i ++)
54               sum += fabs(x*a[i] - b[i]);
55           return sum;
56         }
57         double findSuitableDensity(vector <int> a, vector <int>b)
58         {
59            n = a.size();
60            double  ans = 1e9;
61            for(int i = 0 ;i < n;i ++)
62            {
63                double temp = b[i]*1.0/a[i];
64                ans = min(solve(temp,a,b),ans);
65            }
66            return ans;
67         }
68         
69 
70 };

View Code

没有梦想，何谈远方