| #🎜 🎜#n Portée Dans 1e14 : 🎜🎜# | O (√n)# 🎜🎜#Trouver des diviseurs et des diviseurs |
|
Greedy :
Greedy signifie faire le choix optimal actuel à chaque étape. Les problèmes généralement résolus présentent les caractéristiques suivantes : l'optimalité locale peut conduire à l'optimalité globale.
Veuillez noter que la cupidité n’est pas une panacée !
Il y a n articles. Chaque élément a une valeur v[i] et un poids w[i].
Prenez maintenant les objets dont le poids total ne dépasse pas m. Quelle est la valeur maximale des objets emportés ? (Problème du sac à dos)
Stratégie 1 : Organiser par ordre décroissant de valeur, en prenant à chaque fois la valeur la plus élevée.
Stratégie 2 : Classer par ordre croissant de poids, en prenant à chaque fois le poids le plus léger.
Stratégie 3 : Organisez par ordre décroissant selon la valeur/poids (c'est-à-dire la valeur unitaire), et prenez à chaque fois celui avec la valeur unitaire la plus élevée.
Énumération :
1. Énumération naïve
Comme son nom l'indique, utilisez une boucle for pour énumérer toutes les situations.
2. Énumération état-pression
Utilisez les propriétés de n-base pour énumérer.
Convient aux scénarios : il y a n éléments au total, chaque élément a m états, énumérant tous les états de tous les éléments, la complexité est O(m^n).
Comment écrire une énumération d'état binaire :
Problème classique : étant donné n nombres a1, a2...an, chaque nombre est facultatif, listez toutes les solutions possibles.
for(int i=0;i<1<<n;i++){ //i为1到2^n的状态压缩值 2^n
int p=i; //先将i取出
int sum=0; //用一个变量维护取出的数之和
for(j=0;j<n;j++){ //转为二进制进行操作
sum+=p%2*a[j]; //这句话是求取出来的数之和。p%2为对应二进制位
//这里也可以进行其他操作，不一一举例。
p/=2; //求下一个二进制位
}
//这里可以添加想要的操作。
}Algorithme Question 1 :
chika et satsuma (en utilisant PriorityQueue+Comparator)
Difficulté ⭐⭐
chika aime beaucoup manger des satsumas. Chaque mandarine a un certain degré d’acidité et de douceur. Chika aime manger des oranges sucrées, mais pas des oranges acides.
Chika a mangé k mandarines. Il y a n mandarines au total. Elle calculera la somme de la douceur et de l'acidité des mandarines qu'elle a mangées. Chika veut obtenir la plus grande somme de douceur possible. S'il existe plusieurs options, elle souhaite que l'acidité totale soit aussi faible que possible.
Elle veut savoir, quelle est l'acidité totale finale et la douceur totale ?
Informations sur la question : triez d'abord par douceur dans l'ordre décroissant, puis par acidité dans l'ordre croissant (conservez d'abord l'ordre décroissant précédent de douceur et d'acidité ascendante ensuite)
Description de l'entrée :
La première ligne contient deux entiers positifs n et k représente respectivement le nombre total de mandarines et le nombre de mandarines mangées par Chika. (1≤k≤n≤200000)
La deuxième ligne contient n entiers positifs ai, représentant l'acidité de chaque mandarine. (1≤ai≤1e9)
La deuxième ligne comporte n entiers positifs bi, représentant la douceur de chaque mandarine. (1≤bi≤1e9)
Description de la sortie :
Deux entiers positifs, séparés par des espaces. Représentent respectivement l’acidité totale et la douceur totale.
Exemple
Entrée
3 2
1 3 4
2 2 5
Sortie
5 7
Instructions
Sélectionnez le numéro 1 et Mandarines n°3, l'acidité totale est 5 , total Le niveau de douceur est de 7, ce qui est la solution optimale.
import java.io.*;
import java.util.*;
public class Main{
public static class Orange{
int acid;
int sweet;
public Orange(int acid, int sweet){
this.acid = acid;
this.sweet = sweet;
}
public Orange(){}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
int n = Integer.parseInt(tmp[0]);
int k = Integer.parseInt((tmp[1]));
String[] ai = br.readLine().split(" ");
String[] bi = br.readLine().split(" ");
//定义一个优先队列，并根据指定的比较器对其元素进行排序。
PriorityQueue<Orange> queue = new PriorityQueue<>((Orange o1, Orange o2)->{
//匿名内部类以lambda的形式定义排序规则
if(o1.sweet == o2.sweet){
return o1.acid - o2.acid;
}else{
return o2.sweet - o1.sweet;
}
});
for(int i = 0; i < n; i++){
Orange orange = new Orange();
orange.acid = Integer.parseInt(ai[i]);
orange.sweet = Integer.parseInt(bi[i]);
queue.add(orange);
}
long totalAcid = 0;
long totalSweet = 0;
for(int i = 0; i < k; i++){
Orange o = queue.poll();
totalAcid += o.acid;
totalSweet += o.sweet;
}
System.out.println(totalAcid + " " + totalSweet);
}
}Objectif :
Comprenez ce qu'est la cupidité et vous pouvez envisager d'utiliser PriorityQueue+Comparator lors de la conception avec priorité.
Question algorithme 2 :
toi et le voilier
Difficulté ⭐⭐
Ton père est capitaine. Vous aimez donc la mer depuis que vous êtes enfant. Ce jour-là, elle embarque sur un voilier.
Il existe de nombreux trésors sur la mer, et les coordonnées de chaque trésor sont connues. Vos coordonnées initiales sont (0,0). Elle souhaite explorer deux trésors puis revenir au point de départ.
Vous souhaitez que le parcours soit le plus court possible. Elle voulait savoir quelle était la longueur du chemin le plus court ?
Informations sur la question : Énumérez les deux boucles for et enregistrez le chemin le plus court.
Description de l'entrée :
La première ligne est un entier positif n, représentant le nombre de trésors. (2≤n≤2000)
Les n lignes suivantes, chaque ligne contient 2 entiers positifs xi, yi, représentant les coordonnées du i-ème trésor (-3000≤xi,yi≤3000)
Il n'y a aucune garantie que il n'y en aura pas deux. L'emplacement du trésor est le même. Cela signifie que vous pouvez explorer les deux trésors au même endroit.
Description de la sortie :
La longueur de l'itinéraire le plus court. Gardez 6 chiffres après la virgule.
Exemple
Entrée
2
1 0
0 1
Sortie
3.414214
Explication
import java.io.*;
import java.util.*;
class Point{
double x;
double y;
}
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Point[] points = new Point[n];
for(int i=0;i<n;i++){
String[] strings = br.readLine().split(" ");
Point point = new Point();
point.x = Integer.parseInt(strings[0]);
point.y = Integer.parseInt(strings[1]);
points[i] = point;
}
double min = Double.MAX_VALUE;//定义最大值，寻找较小值
//双层遍历枚举
for (int i=0;i<n-1;i++) {
for (int j=i+1;j<n;j++) {
double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)
+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)
+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));
min = Math.min(min, temp);
}
}
System.out.println(String.format("%.6f", min));
}
} Objectif :
Comprendre ce qu'est une énumération, même si elle en est une par un Listé, mais il existe encore des moyens d'optimiser en fonction de la réalité.
Par exemple, la boucle à deux niveaux dans cette question n'énumère que la moitié de la situation : car ce que l'on cherche, c'est la distance, qui n'a rien à voir avec les deux extrémités.
Réflexion :
Et s'il y a plus de deux coffres au trésor à obtenir ? ? ? Vous pouvez vous référer à la question suivante.
Algorithme Question 3 :
Coloriage numérique
Difficulté ⭐⭐⭐
Xiaohong a obtenu un entier positif X. Elle pourrait teindre certains chiffres en rouge. Ensuite, elle voulait que la somme de tous les chiffres colorés en rouge soit égale à la somme des chiffres non teints.
Elle ne sait pas si elle peut atteindre son objectif. Pouvez-vous lui dire ?
Description de l'entrée :
Un entier positif X, 1
Exemple 1
Entrée
1234567
Sortie
Oui
InstructionsIl suffit de teindre 3, 4 et 7 en rouge, donc 3+4+7=1+2+5+ 6
Exemple 2
Entrée
23
Sortie
Non
Explication
显然无论如何都不能完成染色。
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Long x= Long.parseLong(br.readLine());
//循环0到2^18来展现所有的可能性
for(int i=0;i<1<<19;i++){
long p=i,s1=0,s2=0,temp=x;
//将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。
for(int j=0;j<19;j++){
if(p%2==1)s1+=temp%10;
else s2+=temp%10;
p/=2;
temp/=10;
}
if(s1==s2){
System.out.println("Yes");
System.exit(0);
}
}
System.out.println("No");
}
}这题使用的是状压枚举
只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）
for(int i=0;i<1<<19;i++)
//修改成
for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;
for(int i=0;i<p1[i];i++){}当然这题也可以使用背包或dfs来解答。
算法题4：
ranko的手表
难度 ⭐⭐⭐⭐
ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。
Ranko checked the time at t1 and then again at t2 after some time had passed.。她想弄清楚t1和t2两个时间点之间的最大和最小时间间隔是多少
保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。
输入描述:
两行输入两个时间，为 xx:xx 的形式。x可以是数字或字符'?'，当为'?'时表示该数字未显示。保证输入是合法的。
输出描述:
一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。
示例1
输入
18:0?
2?:1?
输出
121 319
说明
相距最小的时间为 18:09 到 20:10 ，相距121分钟。
相距最大的时间为 18:00 到 23:19 ，相距319分钟。
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s1 = br.readLine();
String s2 = br.readLine();
ArrayList<Integer> a1 = new ArrayList<>();
ArrayList<Integer> a2 = new ArrayList<>();
for(int i = 0; i < 60*24; i++){
int hour = i/60, minute = i%60;
if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&
(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&
(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&
(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);
if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&
(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&
(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&
(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);
}
int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for(int i = 0; i<a1.size();i++){
for(int j = 0; j<a2.size();j++){
if(a1.get(i)<a2.get(j)){
min = Math.min(min,a2.get(j)-a1.get(i));
max = Math.max(max,a2.get(j)-a1.get(i));
}
}
}
System.out.print(min + " " + max);
}
}
