codeforces 996 E. Leaving the Bar

2019-04-14 12:19发布

站内文章 / 模拟电子
12612 0 1454
题目：点击打开链接
题意：给定一些向量，你可以改变它的符号，使得这些向量之和的长度小于1.5e6。
分析：注意有方向，可以将速度分解成为x，y轴方向上的分量，每次贪心取最小，因为每次我贪心原则是一样的，最后的结果有可能大于1.5e6 ，我们需要加一些随机性,，多次贪心，直到结果满足题意。正解是每三个向量中都能找到两个向量合起来 <= 1e6，然后不断合并，最后只会剩下一个或者两个向量，如果一个向量肯定 <= 1e6， 如果是两个向量一定 <= 1.5 * 1e6。
代码：#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define debug test #define mst(ss,b) memset((ss),(b),sizeof(ss)) #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define inf 0x3f3f3f3f #define eps 1e-10 #define MOD 1000000007 #define PI acos(-1.0) const int N = 3e5+10; const ll pp = 1500000; ll gcd(ll p,ll q) { return q==0?p:gcd(q,p%q); } int to[4][2]= {{-1,0},{1,0},{0,-1},{0,1}}; int n; struct nd { ll x,y; int id; } p[N]; int a[N]; ll d(ll a,ll b) { return a*a+b*b; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; for(int i=1; i<=n; i++) { cin>>p[i].x>>p[i].y; p[i].id=i; } while(1) { random_shuffle(p+1,p+n+1); ll x=0,y=0; for(int i=1; i<=n; i++) { if(d(x-p[i].x,y-p[i].y)

热门文章