今天在codeforce刷到了一道C題，感徑訓很有意思，主要用到了貪心演算法，
該題原地址如下https://codeforces.com/problemset/problem/1626/C
題目截圖如下：
簡要翻譯：你正在玩一款魔法類游戲，你需要擊倒你遇到的每一個怪物，你的攻擊充能機制如下：你可在任意時刻進行攻擊，但如果你在該時刻前一秒未攻擊，你的攻擊力只有1，攻擊力會隨著你持續攻擊而升高，同時會耗費與攻擊力等量的能量，例如你在第x秒攻擊第一次，攻擊力為1，耗費1點能量；在第x+1秒攻擊第二次，攻擊力加1，變為2，，耗費2點能量，以此類推，現在給出怪物出現時間與血量的一 一對應序列，要求在怪物出現時必須將其打倒，想要將怪物打倒攻擊力應大于等于怪物的血量，最后統計整個程序耗費的總能量，我們在本題要求該值達到最小，
上來的思路一般是從前往后遍歷，但會出現之前充能足夠但之后充能不夠的情況，我在這里的方法是區間法：構造一個二元組（a,b），a為起始時間坐標，b為怪物出現時間坐標，b-a為你打倒該怪物需要的充能時間，每個怪物都對應著一個充能區間，區間之間會出現覆寫情況，如果出現這種情況，說明兩段充能時間不是獨立的，起始時間坐標應該更新為兩二元組中較小的起始時間坐標；未出現該情況說明獨立，可不更新，本質還是貪心演算法，
代碼如下：
1 /*解決方法：區間覆寫法 2 設定一個結構體存盤頭部坐標與尾部坐標，實作區間的合并 3 */ 4 #include <stdio.h> 5 #include <malloc.h> 6 long long int max (long long int a,long long int b) 7 { 8 if (a>b) 9 return a; 10 else 11 return b; 12 } 13 typedef struct n 14 { 15 long long int start; 16 long long int end; 17 }n; 18 long long int creat_main (long long int num) 19 { 20 long long int point=0; 21 const long long int num1=num; 22 long long int start1=0; 23 n *n1=(n *)malloc(sizeof(n)*num); 24 for (long long int i=0;i<num;i++) 25 scanf("%lld",&n1[i].end); 26 for (long long int i=0;i<num;i++) 27 { 28 scanf("%lld",&start1); 29 n1[i].start=n1[i].end-start1; 30 } 31 for (long long int i=0;i<num1;i++) 32 { 33 for (long long int j=0;j<num1;j++) 34 { 35 if (n1[j].start>=n1[i].start&&n1[j].start<n1[i].end) 36 n1[j].start=n1[i].start; 37 } 38 } 39 long long int final_end=n1[0].end; 40 long long int k0=0; 41 for (long long int i=0;i<num1;i++) 42 { 43 if (num1==1) 44 { 45 point+=(n1[0].end-n1[0].start+1)*(n1[0].end-n1[0].start)/2; 46 break; 47 } 48 if (i==num1-1) 49 { 50 point+=(n1[num1-1].end-n1[num1-1].start+1)*(n1[num1-1].end-n1[num1-1].start)/2; 51 break; 52 } 53 if (n1[i].start==n1[i+1].start) 54 { 55 final_end=max(n1[i].end,n1[i+1].end); 56 continue; 57 } 58 else 59 { 60 point+=(final_end-n1[i].start+1)*(final_end-n1[i].start)/2; 61 final_end=n1[i+1].end; 62 } 63 } 64 return point; 65 } 66 int main (int argc,char *argv[]) 67 { 68 long long int type=0;//次數 69 long long int num=0;//數量 70 long long int point=0; 71 scanf("%lld",&type); 72 const long long int num1=type; 73 long long int *end=(long long int *)malloc(sizeof(long long int)*num1); 74 for (long long int i=0;i<type;i++) 75 { 76 scanf("%lld",&num); 77 point=creat_main(num); 78 end[i]=point; 79 } 80 for (long long int i=0;i<type;i++) 81 printf("%lld\n",end[i]); 82 return 0; 83 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/421827.html
標籤：其他
上一篇：2022-01-27