北京邀请赛 B. Beautiful Garden

约定不等于承诺〃 2021-11-16 06:24 280阅读 0赞

题意：给你坐标和n个点，求最少移动的点使得n个点成等差数列

思路：既然要成等差数列，那么最起码有两个点是不动的，然后枚举这两个点中间的点的个数，近期水的要死，看了队友的代码做的

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    const double eps = 1e-9;
    const int INF = 0x3f3f3f3f;
    
    int n;
    double x[45];
    
    int main() {
    	int cas = 1,t;
    	scanf("%d", &t);
    	while (t--) {
    		scanf("%d", &n);
    		for (int i = 0; i < n; i++) 
    			scanf("%lf", &x[i]);
    		sort(x, x+n);
    		printf("Case #%d: ", cas++);
    		if (n == 1){
    			printf("0\n");
    			continue;
    		}
    		int ans = INF;
    		for (int i = 0; i < n; i++)
    			for (int j = i+1; j < n; j++) 
    				for (int k = 1; k < n; k++) {
    					int count = 0;
    					double d = (x[j]-x[i])/k;
    					double cur = x[i]-d;
    					int cnt = 0;
    					for (int l = 0; l < n; l++) {
    						cur += d;
    						while (x[cnt] < cur && cnt < n)
    							cnt++;
    						if (cnt == n)
    							break;
    						if (fabs(cur-x[cnt]) < eps) {
    							count++;
    							cnt++;	
    						}
    					}
    					ans = min(ans, n-count);
    				}
    		printf("%d\n", ans);
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/ldxsuanfa/p/10894130.html

发表评论取消回复

表情：

评论列表（有 0 条评论，280人围观）

还没有评论，来说两句吧...

相关阅读

相关【构造】Codeforces Round #843 (Div. 2) B Gardener and the Array

[Problem - B - Codeforces][] 题意：给定一个序列，让你判断是否存在两个子序列使得这两个子序列或起来相等思路：设两个子序列是a和b 两

女爷i/ 2024年03月30日 17:28/ 0 赞/ 68 阅读

相关 Beautiful Year

Beautiful Year Time Limit: 1000MS Memory Limit: 65536KB Problem Description It s

迈不过友情╰/ 2022年09月26日 02:35/ 0 赞/ 143 阅读

相关 2014北京邀请赛(部分题解)

马上要去比赛了。今天做了一下2014北京邀请赛，出了两道题目，感觉很水啊、、、首先H题： H. Happy Reversal Time Limit: 1000m

骑猪看日落/ 2022年08月27日 08:49/ 0 赞/ 163 阅读

相关 Beautiful Year

Beautiful Year Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 It

红太狼/ 2022年08月18日 02:24/ 0 赞/ 160 阅读

相关 Beautiful Website

1、公司团体 [Shatara][] [Kings of Code][] [Ecoki][] 2、设计 [Digicoal][][Smashing Magazine][]

清疚/ 2022年01月06日 17:07/ 0 赞/ 214 阅读

相关 Web Farm & Web Garden

尽管Web garden和Web farm存在某些共同特征，但是，Web garden和Web farm是完全不同的概念。Web garden是由运行于一台服务器中的多个进程组

绝地灬酷狼/ 2022年01月06日 13:03/ 0 赞/ 187 阅读

相关北京邀请赛 B. Beautiful Garden

题意：给你坐标和n个点，求最少移动的点使得n个点成等差数列思路：既然要成等差数列，那么最起码有两个点是不动的，然后枚举这两个点中间的点的个数，近期水的要死，看了队友的代码做

约定不等于承诺〃/ 2021年11月16日 06:24/ 0 赞/ 281 阅读

相关 Vue Beauty

链接：vue UI框架 [https://fe-driver.github.io/vue-beauty/\/components/button][https_fe-drive

╰+哭是因爲堅強的太久メ/ 2021年09月16日 02:26/ 0 赞/ 204 阅读

相关 1265 - B. Beautiful Numbers

[Beautiful Numbers][] 思路：先想想暴力的方法，对于m把从一到m每个数的位置求出来，如果最右边的减最左边的数+1等于m,则说明所有数覆盖的范围刚好是m

痛定思痛。/ 2021年07月17日 02:20/ 0 赞/ 325 阅读

相关 Beautiful Soup

1. Beautiful Soup的简介 Beautiful Soup 是用Python写的一个HTML/XML的解析器，它可以很好的处理不规范标记并生成剖析树(pars...

亦凉/ 2021年05月03日 16:23/ 0 赞/ 382 阅读