29 | 1月 | 2016 | 超客的水墨烟雨

poj2653

29 1月 2016

Pick-up sticks

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input

Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

Output

For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.

The picture to the right below illustrates the first case from input.

Sample Input

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0

Sample Output

Top sticks: 2, 4, 5.

Top sticks: 1, 2, 3.

Hint

Huge input,scanf is recommended.

Source

Waterloo local 2005.09.17

题目类型：线段相交

算法分析：直接双重枚举判断每个线段是否与被后边的线段相交即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 20:44:22
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 66;

int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1;
}

struct Point
{
	double x, y;
	Point () {}
	Point (double xx, double yy) : x (xx), y (yy) {}


	Point operator - (const Point &a) const
	{
		return Point (x - a.x, y - a.y);
	}

	double operator ^ (const Point &a) const
	{
		return x * a.y - y * a.x;
	}

	double operator * (const Point &a) const
	{
		return x * a.x + y * a.y;
	}
};

struct Line
{
	Point s, e;
	Line () {}
	Line (Point ss, Point ee) : s (ss), e (ee) {}
};

int n;
Line l[maxn];
vector <int> res;

bool Inter (Line l1, Line l2)
{
	return 
	max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&
	max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&
	max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&
	max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&
	sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&
	sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == 0) break;
		for (int i = 1; i <= n; i++)
			scanf ("%lf%lf%lf%lf", &l[i].s.x, &l[i].s.y, &l[i].e.x, &l[i].e.y);
		
		res.clear ();
		for (int i = 1; i <= n; i++)
		{
			bool is_over = false;
			for (int j = i + 1; j <= n; j++)
				if (Inter (l[i], l[j]))
				{
					is_over = true;
					break;
				}
			if (!is_over)
				res.push_back (i);
		}
		
		printf ("Top sticks:");
		for (int i = 0; i < res.size (); i++)
		{
			if (i == res.size () - 1)
				printf (" %d.\n", res[i]);
			else
				printf (" %d,", res[i]);
		}
	}
    return 0;
}

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

130

131

132

133

134

135

136

137

138

139

140

141

142

/*************************************************

Author :supermaker

Created Time :2016/1/29 20:44:22

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 66;

int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

struct Point

{

double x, y;

Point () {}

Point (double xx, double yy) : x (xx), y (yy) {}

Point operator - (const Point &a) const

{

return Point (x - a.x, y - a.y);

}

double operator ^ (const Point &a) const

{

return x * a.y - y * a.x;

}

double operator * (const Point &a) const

{

return x * a.x + y * a.y;

}

};

struct Line

{

Point s, e;

Line () {}

Line (Point ss, Point ee) : s (ss), e (ee) {}

};

int n;

Line l[maxn];

vector <int> res;

bool Inter (Line l1, Line l2)

{

return

max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&

max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&

max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&

max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&

sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&

sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d", &n) != EOF)

{

if (n == 0) break;

for (int i = 1; i <= n; i++)

scanf ("%lf%lf%lf%lf", &l[i].s.x, &l[i].s.y, &l[i].e.x, &l[i].e.y);

res.clear ();

for (int i = 1; i <= n; i++)

{

bool is_over = false;

for (int j = i + 1; j <= n; j++)

if (Inter (l[i], l[j]))

{

is_over = true;

break;

}

if (!is_over)

res.push_back (i);

}

printf ("Top sticks:");

for (int i = 0; i < res.size (); i++)

{

if (i == res.size () - 1)

printf (" %d.\n", res[i]);

else

printf (" %d,", res[i]);

}

return 0;

}

poj1556

maksyuki 发表于 oj 分类，标签: 图论-最短路, 计算几何-点线面\点积\叉积

29 1月 2016

The Doors

You are to find the length of the shortest path through a chamber containing obstructing walls. The chamber will always have sides at x = 0, x = 10, y = 0, and y = 10. The initial and final points of the path are always (0, 5) and (10, 5). There will also be from 0 to 18 vertical walls inside the chamber, each with two doorways. The figure below illustrates such a chamber and also shows the path of minimal length.

Input

The input data for the illustrated chamber would appear as follows.

2
4 2 7 8 9
7 3 4.5 6 7

The first line contains the number of interior walls. Then there is a line for each such wall, containing five real numbers. The first number is the x coordinate of the wall (0 < x < 10), and the remaining four are the y coordinates of the ends of the doorways in that wall. The x coordinates of the walls are in increasing order, and within each line the y coordinates are in increasing order. The input file will contain at least one such set of data. The end of the data comes when the number of walls is -1.

Output

The output should contain one line of output for each chamber. The line should contain the minimal path length rounded to two decimal places past the decimal point, and always showing the two decimal places past the decimal point. The line should contain no blanks.

Sample Input

1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1

Sample Output

10.00

10.06

Source

Mid-Central USA 1996

题目类型：线段相交+最短路

算法分析：由题易知只有每次走门的端点而不是走中间才能保证两点之间的边是最短的。枚举任意两点构造线段判断是否与图中的竖墙的分隔线段相交，分类讨论之后在满足条件的点之间连边，最后跑一个最短路即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 18:24:35
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100 + 66;

int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1; 
}

struct Point
{
	double x, y;
	Point () {}
	Point (double xx, double yy) : x (xx), y (yy) {}

	Point operator - (const Point &a) const
	{
		return Point (x - a.x, y - a.y);
	}

	double operator ^ (const Point &a) const
	{
		return x * a.y - y * a.x;
	}

	double operator * (const Point &a) const
	{
		return x * a.x + y * a.y;
	}
};

struct Line
{
	Point s, e;
	Line () {}
	Line (Point ss, Point ee) : s (ss), e (ee) {}
};

Point p[maxn];
Line l[maxn];
int n;
double edge[maxn][maxn], dis[maxn];;

double Dist (Point p1, Point p2)
{
	return sqrt ((p2 - p1) * (p2 - p1));
}

bool inter (Line l1, Line l2)
{
	return 
	max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&
	max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&
	max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&
	max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&
	sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&
	sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;
}

void Dij (int s)
{
	fill (dis, dis + maxn, INF);
	dis[s] = 0;
	priority_queue <pair <int, double>, vector <pair <int, double> >, greater <pair <int, double> > > qu;
	qu.push (pair <int, double> (s, 0));
	while (!qu.empty ())
	{
		pair <int, double> tt = qu.top (); qu.pop ();
		int ta = tt.first;
		double tb = tt.second;
		if (sgn (dis[ta] - tb) < 0) continue;
		for (int i = 1; i <= 4 * n + 2; i++)
			if (i != s && edge[ta][i] < INF && dis[i] > edge[ta][i] + dis[ta])
			{
				dis[i] = edge[ta][i] + dis[ta];
				qu.push (pair <int, double> (i, dis[i]));
			}
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == -1) break;
		
		p[1] = Point (0, 5);
		p[4*n+2] = Point (10, 5);
		int tota = 1, totb = 0;
		for (int i = 1; i <= n; i++)
		{
			double x, y;
			scanf ("%lf", &x);
			for (int j = 1; j <= 4; j++)
			{
				scanf ("%lf", &y);	
				p[++tota] = Point (x, y);	
				if (j == 1)
					l[++totb] = Line (Point (x, 0), Point (x, y));
				else if (j == 3)
					l[++totb] = Line (Point (p[tota-1].x, p[tota-1].y), Point (x, y));
				else if (j == 4)
					l[++totb] = Line (Point (x, y), Point (x, 10));
			}	
		}
		
		for (int i = 0; i < maxn; i++)
			for (int j = 0; j < maxn; j++)
				edge[i][j] = INF;

		for (int i = 1; i <= 4 * n + 2; i++)
			for (int j = i + 1; j <= 4 * n + 2; j++)
			{
				int cnt = 0;
				for (int k = 1; k <= 3 * n; k++)
				{
					Line tt = Line (p[i], p[j]);
					if (inter (tt, l[k]))
						cnt++;
				}
				if (i == 1 && j < 4 * n + 2 && cnt == 1) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i == 1 && j == 4 * n + 2 && cnt == 0) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i != 1 && j < 4 * n + 2 && cnt == 2) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i != 1 && j == 4 * n + 2 && cnt == 1) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
			}
		
		for (int i = 1; i <= n; i++)
		{
			int ta = 4 * i - 2, tb =  ta + 1;
			edge[ta][ta+2] = edge[ta+2][ta] = INF;
			edge[tb][tb+2] = edge[tb+2][tb] = INF;
		}
		Dij (1);
		//for (int i = 1; i <= 4 * n + 2; i++)
	//	{
	//		for (int j = 1; j <= 4 * n + 2; j++)
	//			if (edge[i][j] < INF)
	//				cout << "i:" << i << " j:" << j << " edge[i][j]:" << edge[i][j] << endl;
	//	}
		printf ("%.2f\n", dis[4*n+2]);
	}
    return 0;
}

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

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

/*************************************************

Author :supermaker

Created Time :2016/1/29 18:24:35

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 66;

int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

struct Point

{

double x, y;

Point () {}

Point (double xx, double yy) : x (xx), y (yy) {}

Point operator - (const Point &a) const

{

return Point (x - a.x, y - a.y);

}

double operator ^ (const Point &a) const

{

return x * a.y - y * a.x;

}

double operator * (const Point &a) const

{

return x * a.x + y * a.y;

}

};

struct Line

{

Point s, e;

Line () {}

Line (Point ss, Point ee) : s (ss), e (ee) {}

};

Point p[maxn];

Line l[maxn];

int n;

double edge[maxn][maxn], dis[maxn];;

double Dist (Point p1, Point p2)

{

return sqrt ((p2 - p1) * (p2 - p1));

}

bool inter (Line l1, Line l2)

{

return

max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&

max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&

max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&

max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&

sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&

sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;

}

void Dij (int s)

{

fill (dis, dis + maxn, INF);

dis[s] = 0;

priority_queue <pair <int, double>, vector <pair <int, double> >, greater <pair <int, double> > > qu;

qu.push (pair <int, double> (s, 0));

while (!qu.empty ())

{

pair <int, double> tt = qu.top (); qu.pop ();

int ta = tt.first;

double tb = tt.second;

if (sgn (dis[ta] - tb) < 0) continue;

for (int i = 1; i <= 4 * n + 2; i++)

if (i != s && edge[ta][i] < INF && dis[i] > edge[ta][i] + dis[ta])

{

dis[i] = edge[ta][i] + dis[ta];

qu.push (pair <int, double> (i, dis[i]));

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d", &n) != EOF)

{

if (n == -1) break;

p[1] = Point (0, 5);

p[4*n+2] = Point (10, 5);

int tota = 1, totb = 0;

for (int i = 1; i <= n; i++)

{

double x, y;

scanf ("%lf", &x);

for (int j = 1; j <= 4; j++)

{

scanf ("%lf", &y);

p[++tota] = Point (x, y);

if (j == 1)

l[++totb] = Line (Point (x, 0), Point (x, y));

else if (j == 3)

l[++totb] = Line (Point (p[tota-1].x, p[tota-1].y), Point (x, y));

else if (j == 4)

l[++totb] = Line (Point (x, y), Point (x, 10));

}

for (int i = 0; i < maxn; i++)

for (int j = 0; j < maxn; j++)

edge[i][j] = INF;

for (int i = 1; i <= 4 * n + 2; i++)

for (int j = i + 1; j <= 4 * n + 2; j++)

{

int cnt = 0;

for (int k = 1; k <= 3 * n; k++)

{

Line tt = Line (p[i], p[j]);

if (inter (tt, l[k]))

cnt++;

}

if (i == 1 && j < 4 * n + 2 && cnt == 1)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i == 1 && j == 4 * n + 2 && cnt == 0)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i != 1 && j < 4 * n + 2 && cnt == 2)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i != 1 && j == 4 * n + 2 && cnt == 1)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

}

for (int i = 1; i <= n; i++)

{

int ta = 4 * i - 2, tb = ta + 1;

edge[ta][ta+2] = edge[ta+2][ta] = INF;

edge[tb][tb+2] = edge[tb+2][tb] = INF;

}

Dij (1);

//for (int i = 1; i <= 4 * n + 2; i++)

// {

// for (int j = 1; j <= 4 * n + 2; j++)

// if (edge[i][j] < INF)

// cout << "i:" << i << " j:" << j << " edge[i][j]:" << edge[i][j] << endl;

// }

printf ("%.2f\n", dis[4*n+2]);

}

return 0;

}

poj3111

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

29 1月 2016

K Best

Demy has n jewels. Each of her jewels has some value v_i and weight w_i.

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i₁, i₂, …, i_k} as

Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.

Input

The first line of the input file contains n — the number of jewels Demy got, and k — the number of jewels she would like to keep (1 ≤ k ≤ n ≤ 100 000).

The following n lines contain two integer numbers each — v_i and w_i (0 ≤ v_i ≤ 10⁶, 1 ≤ w_i ≤ 10⁶, both the sum of all v_i and the sum of all w_i do not exceed 10⁷).

Output

Output k numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.

Sample Input

3 2
1 1
1 2
1 3

Sample Output

1 2

Source

Northeastern Europe 2005, Northern Subregion

题目类型：最大化平均值(二分)

算法分析：原问题可以转化为求解”单位价值大于等于x”的最大的x。则每次判断是否满足拿k个物品使得vi-x*wi大于等于0，对于满足条件的方案要记录下来。当然这里要贪心地拿最高的k个。注意这里卡STL！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 13:17:22
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

struct point
{
	int v, w, id;	
	double y;
	bool operator < (const point &a) const
	{
		return y > a.y;
	}
};

int n, k;
point aa[maxn];

inline int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1;
}

bool TT (double x)
{
	for (int i = 1; i <= n; i++)
		aa[i].y = aa[i].v - x * aa[i].w;
	sort (aa + 1, aa + 1 + n);

	double ans = 0;
	for (int i = 1; i <= n && i <= k; i++)
		ans += aa[i].y;

	if (sgn (ans) >= 0) return true;
	else return false;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf ("%d%d", &aa[i].v, &aa[i].w);
			aa[i].id = i;
		}

		double low = 0, high = 3e6, mid;
		int tot = 1;
		while (tot <= 100)
		{
			mid = (low + high) / 2.0;
			if (TT (mid)) low = mid;
			else high = mid;
			tot++;
		}
		
		for (int i = 1; i <= k; i++)
		{
			if (i == 1) printf ("%d", aa[i].id);
			else printf (" %d", aa[i].id);
		}
		puts ("");
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

/*************************************************

Author :supermaker

Created Time :2016/1/29 13:17:22

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

struct point

{

int v, w, id;

double y;

bool operator < (const point &a) const

{

return y > a.y;

}

};

int n, k;

point aa[maxn];

inline int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

bool TT (double x)

{

for (int i = 1; i <= n; i++)

aa[i].y = aa[i].v - x * aa[i].w;

sort (aa + 1, aa + 1 + n);

double ans = 0;

for (int i = 1; i <= n && i <= k; i++)

ans += aa[i].y;

if (sgn (ans) >= 0) return true;

else return false;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &k) != EOF)

{

for (int i = 1; i <= n; i++)

{

scanf ("%d%d", &aa[i].v, &aa[i].w);

aa[i].id = i;

}

double low = 0, high = 3e6, mid;

int tot = 1;

while (tot <= 100)

{

mid = (low + high) / 2.0;

if (TT (mid)) low = mid;

else high = mid;

tot++;

}

for (int i = 1; i <= k; i++)

{

if (i == 1) printf ("%d", aa[i].id);

else printf (" %d", aa[i].id);

}

puts ("");

}

return 0;

}

poj2976

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

29 1月 2016

Dropping tests

In a certain course, you take n tests. If you get a_i out of b_i questions correct on test i, your cumulative average is defined to be. Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating a_i for all i. The third line contains n positive integers indicating b_i for all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

Sample Input

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

Sample Output

100

Hint

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

Source

Stanford Local 2005

题目类型：最大化平均值(二分)

算法分析：原问题可以转化为求解”单位价值大于等于x”的最大的x。则每次判断是否满足拿n-k的物品使得vi-x*wi大于等于0，当然这里要贪心地拿最高的k个

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 12:47:33
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e3 + 66;

int v[maxn], w[maxn], n, k;
double aa[maxn];

int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1;
}

bool TT (double x)
{
	for (int i = 1; i <= n; i++)
		aa[i] = v[i] - x * w[i];
	sort (aa + 1, aa + 1 + n, greater <double> ()); 

	double res = 0;
	for (int i = 1; i <= n && i <= n - k; i++)
		res += aa[i];
	
	if (sgn (res) >= 0) return true;
	return false;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		if (n == 0 && k == 0) break;
		for (int i = 1; i <= n; i++)
			scanf ("%d", &v[i]);

		for (int i = 1; i <= n; i++)
			scanf ("%d", &w[i]);
	
		double low = 0, high = 6e16, mid;
		int tot = 1;
		while (tot <= 100)
		{
			mid = (low + high) / 2.0; 
			if (TT (mid)) low = mid;
			else high = mid;
			tot++;
		}

		printf ("%.lf\n", mid * 100);
	}
    return 0;
}

100

101

102

103

104

105

106

/*************************************************

Author :supermaker

Created Time :2016/1/29 12:47:33

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e3 + 66;

int v[maxn], w[maxn], n, k;

double aa[maxn];

int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

bool TT (double x)

{

for (int i = 1; i <= n; i++)

aa[i] = v[i] - x * w[i];

sort (aa + 1, aa + 1 + n, greater <double> ());

double res = 0;

for (int i = 1; i <= n && i <= n - k; i++)

res += aa[i];

if (sgn (res) >= 0) return true;

return false;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &k) != EOF)

{

if (n == 0 && k == 0) break;

for (int i = 1; i <= n; i++)

scanf ("%d", &v[i]);

for (int i = 1; i <= n; i++)

scanf ("%d", &w[i]);

double low = 0, high = 6e16, mid;

int tot = 1;

while (tot <= 100)

{

mid = (low + high) / 2.0;

if (TT (mid)) low = mid;

else high = mid;

tot++;

}

printf ("%.lf\n", mid * 100);

}

return 0;

}

超客的水墨烟雨

poj2653

poj1556

poj3111

poj2976

分类目录

标签云

书签

近期评论

2016年1月
一	二	三	四	五	六	日
« 12月				2月 »
				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