import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
final int N = 50010, M = 500007;
long[] h = new long[M];
int[] id = new int[M];
boolean[] st = new boolean[M];
Circle[] cir = new Circle[N];
final long NULL = Long.MIN_VALUE;
int sqr(int x) {
return x * x;
}
long get_key(int x, int y) {
return (long)x * 1000000000 + y;
}
// 如果(x, y)存在， 返回它在数组中的下标， 否则返回应该插入的位置
int find(int x, int y) {
long key = get_key(x, y);
int t = (int) ((key % M + M) % M);
while(h[t] != NULL && h[t] != key) {
t++;
if(t == M) t = 0;
}
return t;
}
void dfs(int x, int y, int r) {
st[find(x, y)] = true;
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
if(sqr(i - x) + sqr(j - y) <= sqr(r)) {
int t = find(i, j);
if(id[t] != 0 && !st[t])
dfs(i, j, cir[id[t]].r);
}
}
}
}
public Main() throws IOException {
// 初始化哈希表
Arrays.fill(h, NULL);
String[] line = in.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
for (int i = 1; i <= n; i++) {
line = in.readLine().split(" ");
int x = Integer.parseInt(line[0]);
int y = Integer.parseInt(line[1]);
int r = Integer.parseInt(line[2]);
cir[i] = new Circle(x, y, r);
int t = find(x, y);
if(h[t] == NULL) h[t] = get_key(x, y);
if(id[t] == 0 || r > cir[id[t]].r) {
id[t] = i;
}
}
while(m-- > 0) {
line = in.readLine().split(" ");
int x = Integer.parseInt(line[0]);
int y = Integer.parseInt(line[1]);
int r = Integer.parseInt(line[2]);
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
if(sqr(i - x) + sqr(j - y) <= sqr(r)) {
int t = find(i, j);
if(id[t] != 0 && !st[t])
dfs(i, j, cir[id[t]].r);
}
}
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
int t = find(cir[i].x, cir[i].y);
if(st[t]) res++;
}
System.out.println(res);
in.close();
}
public static void main(String[] args) throws Exception {
new Main();
}
}
class Circle{
int x, y, r;
public Circle(int x, int y, int r) {
super();
this.x = x;
this.y = y;
this.r = r;
}
}
题目描述
原题链接 https://codeforces.com/contest/1622/problem/C
You are given an integer array a1,a2,…,an and integer k.
In one step you can
either choose some index i and decrease ai by one (make ai=ai−1);
or choose two indices i and j and set ai equal to aj (make ai=aj).
What is the minimum number of steps you need to make the sum of array ∑i=1nai≤k? (You are allowed to make values of array negative).
Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n and k (1≤n≤2⋅105; 1≤k≤1015) — the size of array a and upper bound on its sum.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the array itself.
It’s guaranteed that the sum of n over all test cases doesn’t exceed 2⋅105.
Output
For each test case, print one integer — the minimum number of steps to make ∑i=1nai≤k.
样例
输入:
4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10
输出:
10
0
2
7
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
const int N = 2 * 1e5 + 10;
vector<LL> a;
int t;
LL min(LL a,LL b)
{
return a < b ? a : b;
}
int main()
{
cin >> t;
while(t -- )
{
a.clear();
LL n,k,sum = 0;
cin >> n >> k;
for(int i = 1;i <= n;i++) {
int x;
cin >> x;
sum += x;
a.push_back(x);
}
sort(a.begin(),a.end());
if(k >= sum){
cout<<"0"<<endl;
continue;
}
else{
LL res = sum - k;
LL s = a[0] - res;
for(int i = n - 1;i > 0;i--)
{
s += a[i];
LL x;
int y = n - i + 1;
if(s >= 0) x = s / y;
else x = (s- y + 1) / y;
x = min(x,a[0]);
res = min(res , a[0] - x + y - 1);
}
cout<<res<<endl;
}
}
return 0;
}
本题 要知道’A‘ 对应65 ， ’a‘ 97；
字符串 最后一位 是’\0‘ , 是 Enter 上面的 那个键；
#include<bits/stdc++.h>
using namespace std ;
int main()
{
string s ;
cin >> s ;
for(int i=0,len = s.length(); i<len ; i++)
{
if(s[i] > 64 ) {}// 65 是 A
else
{
int n = s[i] - '0' ;
for(int j=1 ;j<=n ;j++)
{
cout << s[i-1] ;
}
}
if(s[i] > 64 && (s[i+1] >64 || s[i+1] == '\0') )
{
cout << s[i] ;
}
}
return 0;
}
题目讨论
AcWing 94. 递归
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 10;
//全局变量初值为0
int n;
int state[N];//0表示还没放数
bool used[N];//true表示用过
void dfs(int u)
{
if(u>n)//边界
{
for(int i=1;i<=n;i++) cout<<state[i]<<” “;
cout<<endl;
return;
}
//枚举
for(int i=1;i<=n;i++)
{
if(!used[i])
{
state[u]=i;
used[i]=1;
dfs(u+1);
//恢复
state[u]=0;
used[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
题目描述
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16
个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 4×4
的矩阵，您可以改变任何一个位置 [i,j]
上把手的状态。
但是，这也会使得第 i
行和第 j
列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 N
，表示所需的最小切换把手次数。
接下来 N
行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
1≤i,j≤4
输入样例：
-+–
-+–
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4
样例
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
//因为每一行或者每一列都可以改变对应一整行或者一整列的元素，所以一般不能用递推来操作。因为是四成四的矩阵，直接使用暴力算法进行便利
using namespace std;
//因为这里面需要记录方案，所以要开一个数组或者容器，去记录一下方案。
typedef pair <int,int> PII;
const int N =5;
char g[N][N],backup[N][N];
void turn_one(int x,int y)
{
if(g[x][y]=='+') g[x][y]='-';
else g[x][y]='+';
}
void turn_all(int x,int y)
{
for(int i=0;i<4;i++)
{
turn_one(x,i);
turn_one(i,y);
}
turn_one(x,y);
}
int get(int x,int y)
{
return x*4+y;
}
int main()
{
for(int i=0;i<4;i++) cin>>g[i];
vector<PII> res;//存储最终结果方案的一个vector容器，因为要存两个数字，所以用到了pair
memcpy(backup,g,sizeof g);
for(int op=0;op<(1<<16);op++)//这个1<<16表示的的是2^16，用op代表所有可能发生的情况，进行枚举。
{ vector<PII> temp;//创建一个临时的存放结果的地方，为了更好的更新res
//******************************************************//
//这段代码就是便利16位二进制数的每一位 op>>i(i是1-16) 但是这道题目是需要记录下是按了那个开关了，所以要用双重for循环+映射的形式进行操作。
for(int i=0;i<4;i++)
{ for(int j=0;j<4;j++)
{
if(op>>get(i,j)&1)//一共有16个格子，然后发现二进制位是1的就进行操作
{
temp.push_back({i,j});//先把操作的内容记录下来
turn_all(i,j);//进行操作
}
}
}
//**************************************************//
//-----------------------------------------// 检查是否还有没有开着的门
bool has_closed =false ;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(g[i][j]=='+') {has_closed=true;break;}
if(!has_closed){
if(res.empty()||res.size()>temp.size()) res=temp;//找打一个比较优的解，就要把这个目前最优的解赋给最终答案
}
//-------------------------------------------//
memcpy(g,backup,sizeof g);//因为动过了g里面的内容，所以要对g中的内容进行恢复，---恢复现场
}
cout<<res.size()<<endl;
for(auto p:res) cout<<p.first+1<<" "<<p.second+1<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int M=25010;
int a[N];
int dp[M];//dp[N][m];
int cnt;
int main() {
int t;
cin>>t;
while(t--) {
cnt=0;
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
//初始化
memset(dp,0,sizeof dp);//一定要重置为0
dp[0]=1;
for(int i=1;i<=n;i++) {
if(!dp[a[i]]) cnt++;
for(int j=0;j<=a[n];j++) {
if(j>=a[i])
dp[j]+=dp[j-a[i]];
}
}
cout<<cnt<<"\n";
}
return 0;
}
