Bronze埋めなーーーーー

3618

貪欲

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct t {
	int cost, flag;
	t() { flag = 1; }
};
class Comp {
	public:
		bool operator() (const t& a, const t& b) {
			return abs(a.cost) < abs(b.cost);
		}
};
int main() {
	int T, N;
	scanf("%d%d",&T,&N);
	t town[N];
	for (int i=0; i<N; i++) scanf("%d",&town[i].cost);
	int npos = 0, been = 0, res = 0;
	sort(town, town+N, Comp());
	for (res=0; res<N; res++) {
		been += abs(town[res].cost-npos);
		if (been>T) break;
		npos = town[res].cost;
	}
	printf("%d\n", res);
}

3627

貪欲

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n, b;
	scanf("%d%d",&n,&b);
	vector<int> cow(n);
	for (int i=0; i<n; i++) scanf("%d",&cow[i]);
	sort(cow.rbegin(), cow.rend());
	int res, sum=0;
	for (res=0; res<n; res++) {
		if (sum >= b) break;
		sum += cow[res];
	}
	printf("%d\n",res);
}

3628

BFS

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
#define INF INT_MAX
int bfs(int cow[], int npos, int N, int diff, int sum) {
	if (diff<sum) return INF;
	if (npos==N) return diff-sum;
	return min(bfs(cow,npos+1,N,diff,sum+cow[npos]),bfs(cow,npos+1,N,diff,sum));
}
int main() {
	int N, B, sum = 0;
	scanf("%d%d",&N,&B);
	int cow[N];
	for (int i=0; i<N; i++) {
		scanf("%d",&cow[i]);
		sum += cow[i];
	}
	int diff = sum - B;
	printf("%d\n",bfs(cow,0,N,diff,0));
}

3663

やるだけ

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int N, S;
	scanf("%d%d",&N,&S);
	int cows[N];
	for (int i=0; i<N; i++) scanf("%d",&cows[i]);
	sort(cows, cows+N);
	int res = 0;
	for (int i=0; i<N; i++) {
		for (int j=i+1; j<N; j++) {
			if (cows[i]+cows[j]>S) break;
			res++;
		}
	}
	printf("%d\n",res);
}

3664

めんどくせ、カリッ

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
int main () {
	int n, k;
	scanf("%d%d",&n,&k);
	vector<PP> cows(n);
	for (int i=0; i<n; i++) {
		scanf("%d%d",&cows[i].first,&cows[i].second.first);
		cows[i].second.second=i+1;
	}
	sort(cows.rbegin(), cows.rend());
	P res[k];
	for (int i=0; i<k; i++) {
		res[i].first=cows[i].second.first;
		res[i].second=cows[i].second.second;
	}
	sort(res, res+k);
	printf("%d\n", res[k-1].second);
}

3665

やるだけ

#include <cstdio>
#include <algorithm>
using namespace std;
int N, T;
int main() {
	scanf("%d%d", &N,&T);
	int s[N];
	for (int i=0; i<N; i++) scanf("%d",&s[i]);
	for (int i=0; i<T; i++) {
		int res = 0, high = 0;
		for (int i=0; i<N; i++) if (high<s[i]) {
			high = s[i];
			res = i;
		}
		printf("%d\n", res+1);
		int m = s[res]/(N-1);
		int temp = s[res] - m*(N-1);
		for (int i=0; i<N; i++) if (i!=res) {
			s[i] += m;
			if (temp) {
				s[i]++;
				temp--;
			}
		}
		s[res]=0;
	}
}

3671

しきりを動かす

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    int cows[n];
    for (int i=0; i<n; i++) scanf("%d", &cows[i]);
    int res = INT_MAX;
	int dp[2] = {0, 0};	// 1---iまでの2の個数 2---i+1からの1の個数
    for (int i=0; i<n; i++) if (cows[i]==1) dp[1]++;
	res = min(res, dp[0]+dp[1]);
	for (int i=0; i<n; i++) {
		if (cows[i]==2) {
			dp[0]++;
		} else {
			dp[1]--;
		}
		res = min(res, dp[0]+dp[1]);
	}
    printf("%d\n", res);
}